“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

123. The best time to Buy and sell stocks III

The title

Given an array, its ith element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1

Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), this transaction will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit of 4-1 = 3.Copy the code

Example 2

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Answer key

Dynamic programming

There are 555 possibilities for analyzing day III returns:

  • No buy, no sell, no action
  • There was only buy, no sell, and it was the first buy
  • There’s only a sale that day, and that’s when you’ve made your first trade, because they’re asking you to make two at most and still be able to buy
  • Bought that day, made the first purchase and made the second purchase
  • Sold the same day, the second deal closed

So the dynamically planned array requires an array DPDPDP that is the length of PricesPricesprices, and each DPDPDP item needs an array of 555 lengths that holds 555 states


var maxProfit = function (prices) {
  // Dynamic programming
  const len = prices.length;
  const dp = [];
  for (let i = 0; i <= len; i++) {
    dp[i] = [0.0.0.0.0];
  }
  // First transaction
  dp[0] [1] = -prices[0];
  dp[0] [3] = -prices[0];
  for (let i = 1; i < len; i++) {
    
    dp[i][0] = dp[i - 1] [0];
    
    // Buy the stock, or the stock is i-1 day stock
    dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
    
    // Sell the stock or keep the stock
    dp[i][2] = Math.max(dp[i - 1] [2], dp[i - 1] [1] + prices[i]);
    
    // Buy the stock, or the stock is i-1 day stock
    dp[i][3] = Math.max(dp[i - 1] [3], dp[i - 1] [2] - prices[i]);
    
    // Sell the stock or keep the stock
    dp[i][4] = Math.max(dp[i - 1] [4], dp[i - 1] [3] + prices[i]);
  }
  
  // Finally return the stock returns
  return dp[len - 1] [4];
};
Copy the code

Dynamic planning + compression space

var maxProfit = function (prices) {
  // Dynamic programming
  const len = prices.length;
  const dp =[0.0.0.0.0];
  dp[1] = -prices[0];
  dp[3] = -prices[0];
  for (let i = 1; i < len; i++) {
    dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    dp[2] = Math.max(dp[2], dp[1] + prices[i]);
    dp[3] = Math.max(dp[3], dp[2] - prices[i]);
    dp[4] = Math.max(dp[4], dp[3] + prices[i]);
  }
  return dp[4];
};
Copy the code