Topic describes

Idea 1: Update the maximum and minimum values

  • First, assume that the first element is minPrice, the lowest price.
  • Define a maximum price difference maxPriceDiff and set the value to 0.
  • Updates the price Max and min values from the second element of the array.
  • The minimum is the comparison between the ith element and the previous minimum minPrice.
  • The maximum price spread is compared between the previous maximum price spread and (the value of the stock on day I – the previous minimum).
  • Finally return the maximum price difference.

AC code

var maxProfit = function (prices) {
    // Update the maximum and minimum values
    let maxPriceDiff = 0;
    let minPrice = prices[0];
    for (let i = 1; i < prices.length; i++) {
        minPrice = Math.min(prices[i], minPrice);
        let tempMax = Math.max(prices[i] - minPrice);
        maxPriceDiff = Math.max(maxPriceDiff, tempMax);
    }
    return maxPriceDiff;
};
Copy the code

Idea 2: Dynamic planning

See comments in the code for details. Note: in this case there is only one transaction, for example if you buy today the cash you have is -prices[I].

Dp array and what the subscripts mean

  • Dp [I][0] : indicates the amount of cash that does not hold shares on day I
  • Dp [I][1] : represents the amount of cash held in stocks on day I

AC code

var maxProfit = function (prices) {
    // By dynamic programming
    const dp = new Array(prices.length).fill([0.0]);
    // Set the initial value for dynamic planning
    // The amount of cash on hand on day 0 without holding shares
    dp[0] [0] = 0;
    // The amount of cash on hand is the negative of the day's price
    dp[0] [1] = -prices[0];
    // Start traversal from the next day
    for (let i = 1; i < prices.length; i++) {
        // Day I no shares in hand: no shares in hand the previous day, or shares in hand the previous day but sold today
        dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]);
        // Day I hold stock situation: the previous day did not hold stock, buy today, or the previous day hold stock today did not sell
        dp[i][1] = Math.max(- prices[i], dp[i - 1] [1]);
    }
    // The final return is the maximum amount of cash that was not held on the last day
    return dp[prices.length - 1] [0]};Copy the code

The title to reflect

  • Learn to use dynamic programming to solve stock buying and selling problems
  • Learn to solve this problem by constantly updating the maximum and minimum values.
  • The most important thing about dynamic programming is to understand the dp array and its subscripts and to list the equations of dynamic programming accurately.