【LeetCode】123.买卖股票的最佳时间

清晰明了的思路是解决问题的至上法宝。如何把一个复杂的问题拆成简单的问题，就是我们需要考虑的。

1. 题目

2. 思想

这道题虽然是难题，但是思想比较简单。

题目要求说至多买卖两次，也就是说，也可以买卖一次，这种情况之前有分析过，比较简单。那么我们就着重看下买卖两次是怎么获取最大收益。

买卖两次那么就必须从中间某一天分割开。比如题中的样例[3,3,5,0,0,3,1,4]，相当于拆成了[3,3,5] [,0,0,3,1,4] 两部分，再求两个小区间的最大值即可。也就是说，需要找出一个分割点，然后使得分割点左侧的钱卖出赚的钱 + 分割点右侧区间卖出赚的钱 最多即可。那么接下来就是计算分割点左侧区间的钱，和分割点右侧区间卖出可以赚的钱。这个计算比较简单，就是直接遍历然后迭代更新出最大值即可。

需要注意的是，买卖两次有时候不如买卖一次赚的钱多，所以最后，需要一起判断最大值是多少。

3. 代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_left = [0] * len(prices)
        dp_right = [0] * len(prices)
        
        cur_min = prices[0]
        for i in range(1,len(prices)):
            dp_left[i] = max(dp_left[i-1], prices[i] - cur_min)
            cur_min = min(cur_min, prices[i])
        print(dp_left)
        
        cur_max = prices[-1]
        for i in reversed(range(len(prices)-1)):
            dp_right[i] = max(dp_right[i+1], cur_max - prices[i] )
            cur_max = max(cur_max, prices[i])
        print(dp_right)

        res = 0
        for i in range(1, len(prices)-1):
            res = max(res,dp_left[i] + dp_right[i+1] )
        return max(res, dp_left[-1], dp_right[0])