Dynamic planning of the best time to buy and sell stocks – JavaScript

The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

1. Analysis of dynamic programming

The price array is prices

1. Delimit the molecular problem and determine the boundary of the sub-problem

• MaxProfit [I +1] = Max(maxProfit[I], prices[I +1] -minprice)

2. Define the optimization function, list the recursive equation of the optimization function, and judge whether it meets the optimization principle

According to the recursive equation (state transition equation), the maximum profit on n days is determined by the maximum profit on n-1 days. Therefore, dynamic subdivision can be used to meet the optimization principle.

3, programming,

The specific program is as follows;

2. Dynamic Scaling (DP)

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {

    const len = prices.length;

    let minPrice = prices[0],
        f = [0];
        

    if(len < 2) {
        return 0;
    } 

    for(let i = 1; i < len; i++) { f[i] =Math.max(f[i-1],prices[i] - minPrice);
        
        if(minPrice > prices[i]) { minPrice = prices[i]; }}return f[len - 1];
    
};
Copy the code

Time and space optimization of the program;

2.1. Optimization time

The loop body in the loop above is:

Method one:

// A calculation, a comparison, an assignment
f[i] = Math.max(f[i-1],prices[i] - minPrice);
// a comparison operation
if(minPrice > prices[i]) {
		// An assignment
		minPrice = prices[i];
}
Copy the code

Method 2:

// a comparison operation
if(minPrice > prices[i]) {
		// Two assignment operations
		minPrice = prices[i];
		f[i] = f[i-1];
}else {
		// A calculation, a comparison, an assignment
		f[i] = Math.max(f[i-1],prices[i] - minPrice);
}
Copy the code

Method 1: At least 4 operations, at most 5 operations; Method two has a minimum of 3 operations (and a more time-efficient assignment) and a maximum of 4 operations;

Theoretically, for a problem of the same size, method one takes less time than method two;

2.2. Optimize space

In the above program, the space consumption is mainly spent on the array of storage solutions to the storage problem, and the space complexity is O(n). However, the analysis of the code shows that only f(n-1) needs to be known when calculating f(n), and f(I) with I < n-1 does not need to be known. So you can store the maximum profit of a subproblem with just one variable;

The algorithm is as follows:

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {

    const len = prices.length;

    let minPrice = prices[0],
        maxPro = 0;
        

    if(len < 2) {
        return 0;
    } 

    for(let i = 1; i < len; i++) { maxPro =Math.max(maxPro,prices[i] - minPrice);

        if(minPrice > prices[i]) { minPrice = prices[i]; }}return maxPro;
    
};

Copy the code

3. Enumeration of violence

Time consumption is too high, the program can run, but the Leetcode submission exceeds the time limit;

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {

    // Double loop, the outer loop selects a value, the inner loop finds the maximum value of all values after the selected value, and uses the variable to record profits
    let max = 0;
    let temp = 0;
    let tempMax = 0,
        tempj = 0;

    
    const len = prices.length;
    for(let i = 0; i < len; i++) { temp = prices[i];for(let j = i + 1; j < len; j++) { tempj = prices[j];if(temp < tempj) {

                temp = tempj;
            }
        }
        
        tempMax = temp - prices[i];
        if(max < tempMax) { max = tempMax; }}return max;
 
};
Copy the code

If you have a better way of thinking and reconciliation, welcome to discuss ah ~

This is a summary and implementation of each problem in LeetCode’s “Elementary Algorithms” using JavaScript. The summary is here:

Juejin. Cn/post / 700669…