I. Title Description:

Leetcode-cn.com/problems/be… 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

Ii. Analysis of Ideas:

  • Recursive + mnemonic search
  • Three cases:
    • There will be no trading on that day
    • Hold stocks the day before: Can sell stocks today and take the maximum without buying or selling
    • No stock held the previous day: take the maximum value to buy or sell stocks today

Iii. AC Code:

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function (prices) {
    const dp = new Array(prices.length + 1).fill(null).map(_= > new Array(3).fill(null).map(_= > []))
    function getMaxProfitInRange(index, time, status) {
        if (index === prices.length) {
            return 0
        }
        if (time === 2) {
            return 0
        }
        if(dp[index][time][status]! = =undefined) {return dp[index][time][status]
        }
        // hold
        let max = getMaxProfitInRange(index + 1, time, status)
        if (status) {
            // sale
            max = Math.max(max, getMaxProfitInRange(index + 1, time + 1.0) + prices[index])
        } else {
            // buy
            max = Math.max(max, getMaxProfitInRange(index + 1, time, 1) - prices[index])
        }
        dp[index][time][status] = max
        return max
    }
    return getMaxProfitInRange(0.0.0)};Copy the code