123. Best Time to Buy and Sell Stock III 这题解法中的问题

https://leetcode.com/problems/be ... and-sell-stock-iii/
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1,buy2 = -sys.maxsize,-sys.maxsize
        profit1,profit2 = 0,0
        for price in prices:
            buy1 = max(buy1, -price)
            profit1 = max(profit1, buy1 + price)
            buy2 = max(buy2, profit1 - price)
            profit2 = max(profit2, buy2 + price)
        return profit2

其他解我都明白了。
但是请问以上这个解法，是如何防止multiple transactions发生的？

这个问题可以用两种方式来回答，一种是建立数量关系之后推公式，第二种是从状态转移方程的角度定义循环不变式（loop invariants）

第一种方法比较有意思，这里先写一下

首先不妨设prices有n个元素，那么for循环就会循环n次，我们从0开始编号到n-1，记第k次循环结束时各个变量的值分别为 buy1[k]、profit1[k]、buy2[k]、profit2[k]

由代码易知有如下数量关系：

1. (1) buy1[k] = max{ - prices[i] | 对于所有的 0 <= i <= k }
   
2. 
   
3. (2) profit1[k] = max{ buy1[i] + prices[i] | 对于所有的 0 <= i <= k }
   
4. 
   
5. (3) buy2[k] = max{ profit1[i] - prices[i] | 对于所有的 0 <= i <= k }
   
6. 
   
7. (4) profit2[k] = max{ buy2[i] + prices[i] | 对于所有的 0 <= i <= k }

复制代码

给定上面的等式，我们可以证明如下定理：

1. 定理1：profit2[k] = max { prices[j] - prices[i] + prices[v] - prices[u] | 对于所有的 0 <= i <= j <= u <= v <= k }
   

复制代码

然后由定理1立刻可以得到：

1. 推论2: profit2[n-1]（也就是最后一次循环后profit2的值）即是原问题的解
   

复制代码

下面来证明定理1，过程其实很直接，首先对(2)式进行展开：

1. profit1[k] = max{ buy1[i] + prices[i] | 对于所有的 0 <= i <= k }
   
2. 
   
3.            = max{ max{ - prices[i] | 对于所有的 0 <= i <= j }
   
4.                   + prices[j] | 对于所有的 0 <= j <= k }
   
5.                   
   
6.            = max{ prices[i] - prices[j] | 对于所有的 0 <= j <= i <= k }
   

复制代码

然后在此基础上依次对(3)、(4)式展开即可

https://leetcode.com/problems/be ... s-of-stock-problems
这个帖子用的和楼主发的解答应该是同一种做法，可以看看

表达式已经很明显地做了规则的约定。
比如说： buy2 = max(buy2, profit1 - price)
表明buy2只能是由卖掉一只股票之后再买入一只股票得到（profit1 - price）。这个表达式没有允许通过买入一只股票再买入一只股票来实现buy2（那样的话就是buy1-price）、

谢谢楼上各位。