题目地址：Best Time to Buy and Sell Stock III - LeetCode

买股票系列题目：

• LeetCode 121. Best Time to Buy and Sell Stock–Java，Python，C++解法
• LeetCode 122. Best Time to Buy and Sell Stock II–贪心–Java,C++,Python解法
• LeetCode 123. Best Time to Buy and Sell Stock III–Python解法–动态规划–数学题
• LeetCode 309. Best Time to Buy and Sell Stock with Cooldown–Java解法-卖股票系列题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

这道题目乍一看用贪心可以做，可以过题目给的样例，但实际上并不行，考虑样例如下：

[1,3,2,7]

这道题目看起来跟这道很像：LeetCode 122. Best Time to Buy and Sell Stock II–贪心–Java,C++,Python解法，但其实不一样。

感觉应该用动态规划来做，但不好做。

我想不出解法，看了别人的做法，感觉很神奇。

Python解法如下：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []:
            return 0
        buyOne = 0x7ffffff
        SellOne = 0
        buyTwo = 0x7ffffff
        SellTwo = 0
        for p in prices:
            buyOne = min(buyOne, p)
            SellOne = max(SellOne, p - buyOne)
            buyTwo = min(buyTwo, p - SellOne)
            SellTwo = max(SellTwo, p - buyTwo)
        return SellTwo

下面以[1, 3, 2, 7]为例：

可以看出buyOne变量代表的是全局最小值,SellOne变量代表的是只买卖一次股票的全局的最大获利

buyTwo变量表示的是用获利的钱(只买卖一次的全局最多的钱)购买当天股票后剩余的钱，SellTwo变量代表买卖股票2次获利最多的钱。

解法真的很神奇。