123. Best Time to Buy and Sell Stock III

Loading...LeetCode

遍历 prices，对于每个元素（价格）都有三个选择：1.买，2.卖，3.不操作，终止条件也很明确：遍历结束，或买/卖均达到2次。

Backtracking

树形发展的多个sequence里面找合格/最优，我觉得可以试试 backtracking，但这题直接这样写会 TLE，即便已经用了memo.

DP - max future profit

改成 DP 返回当前位置往后可能的 max profit，相当于从终止（0）往前逆增，勉强能过。

Max Rise

基于 121. Best Time to Buy and Sell Stock 解法，在 prices 序列里寻找两个最大增幅区间。

直接在整个prices里面找 max rise 结果是(a, b)，两个最大增幅区间就会有三种情况：

1. 第二个 max rise 在 day a 之前，即 y <= a，那在 prices[:a] 里找一次即可；

2. 第二个 max rise 在 day b 之后，即 x >= b，那在 prices[b:] 里找一次即可；

3. 两个 max rise 分别是 (a, x) 和 (y, b)，即 day x 做了第一次卖出之后，等到价格下降到 day y 又做了第二次买入，那相当于要在 (a, b) 之间找 max drop，实际上就是在prices[b:a]里找 max rise；

DP - State Machine

整个过程里，除了初始状态（没做任何买入）之外，只有四个状态：

1. 第一次 holding stock

2. 第一次 sold stock

3. 第二次 holding stock

4. 第二次 sold stock

设置四个变量来代表四个状态的 max profit，遍历 prices 来更新四个变量。

Easy DP solution using state machine, O(n) time complexity, O(1) space complexity

DP - max previous profit

这个实际上是 188. Best Time to Buy and Sell Stock IV 的 DP 解法，对于每一天的最高 balance，有两个可能的计算方式：

1. 不做任何交易 -> 那就等于前一天的 balance；

2. 卖出股票 -> 那就等于今天的价格减去之前某天 day m 的价格，再加上在 day m 之前做 K-1 笔交易可能的最高 balance；

f[i][j] = max(f[i][j-1], max(prices[j] - prices[m] + f[i-1][m] for m in range(0, j-1)]

188. Best Time to Buy and Sell Stock IV

Max Rise

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        def maxRise(left, right, step):
            prevLow, diff = left, 0
            low, high = 0, 0
            for i in range(left, right, step):
                if prices[i] < prices[prevLow]:
                    prevLow = i
                if prices[i] - prices[prevLow] > diff:
                    diff = prices[i] - prices[prevLow]
                    low, high = prevLow, i
            return (low, high, diff)
        
        
        n = len(prices)
        low, high, rise = maxRise(0, n, 1)
        a, b, c = maxRise(0, low, 1)[2], maxRise(high+1, n, 1)[2], maxRise(high-1, low, -1)[2]
        return rise + max([a, b, c])
            

DP - max previous profits

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1: return 0
        dp = [[0 for _ in range(n)] for _ in range(3)]
        
        # i: how many transaction made
        # j: # of day
        for i in range(1, 3):
            maxDiff = -prices[0]
            for j in range(1, n):
                maxDiff = max(maxDiff, dp[i-1][j-1] - prices[j-1])
                dp[i][j] = max(dp[i][j-1], prices[j] + maxDiff)
                
        return dp[-1][-1]

DP - State Machine

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        A, B, C, D = -prices[0], float("-inf"), float("-inf"), float("-inf")
        for p in prices:
            A = max(A, 0 - p)
            B = max(B, A + p)
            C = max(C, B - p)
            D = max(D, C + p)
        
        return D

DP - max future profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        self.memo = dict()
        
        def maxLocal(idx, buy, sell):
            # ending conditions
            if sell == 2 or idx == len(prices):
                return 0
            if (idx, buy, sell) in self.memo:
                return self.memo[(idx, buy, sell)]
            # keep going
            else:
                hold = maxLocal(idx+1, buy, sell)
                b = maxLocal(idx+1, buy+1, sell) - prices[idx] if (buy < 2 and buy == sell) else float("-inf")
                s = maxLocal(idx+1, buy, sell+1) + prices[idx] if (sell < 2 and buy > sell) else float("-inf")
                self.memo[(idx, buy, sell)] = max([hold, b, s])
                return self.memo[(idx, buy, sell)]
                        
        return maxLocal(0, 0, 0)

Backtracking (TLE)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        self.maxProfit = 0
        memo = set()
        
        def backtrack(idx, buy, sell, balance):
            # ending conditions
            if sell == 2 or idx == len(prices):
                self.maxProfit = max(self.maxProfit, balance)
                return
            if (idx, buy, sell, balance) in memo:
                return 
            # keep going
            else:
                memo.add((idx, buy, sell, balance))
                # do nothing, just wait for next trade day
                backtrack(idx+1, buy, sell, balance)
                # have chance to buy
                if buy < 2 and buy == sell:
                    backtrack(idx+1, buy+1, sell, balance-prices[idx])
                # have chance to sell
                if sell < 2 and buy > sell:
                    backtrack(idx+1, buy, sell+1, balance+prices[idx])
        
        backtrack(0, 0, 0, 0)
        
        return self.maxProfit