给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
2 解析-
对于 第一个状态 d 1 d_1 d1，我们目前持有的这一支股票可以是在第 i−1 天就已经持有的，对应的状态为 d 1 d_1 d1；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 d 3 d_3 d3加上买入股票的负收益 prices[i]。因此状态转移方程为：（理解为买入状态） d 1 = m a x ( d 1 , d 3 − p r i c e s [ i ] ) d_1=max(d_1,d_3−prices[i]) d1=max(d1,d3−prices[i])
-
对于第二个状态 d 2 d_2 d2，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 d 1 d_1 d1加上卖出股票的正收益 prices[i]。因此状态转移方程为：（理解为卖出） d 2 = d 1 + p r i c e s [ i ] d_2=d_1+prices[i] d2=d1+prices[i]
-
对于第三个状态 d 3 d_3 d3，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 d 2 d_2 d2；如果不处于冷冻期，对应的状态为 d 3 d_3 d3。因此状态转移方程为： d 3 = m a x ( d 2 , d 3 ) d_3=max(d_2,d_3) d3=max(d2,d3)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
d_1,d_2,d_3 =-prices[0],0,0
for i in range(1,len(prices)):
# 买入
tmp_d_1 = max(d_1,d_3-prices[i])
# 已经卖出
tmp_d_2 = d_1+prices[i]
# 冻结
tmp_d_3 = max(d_2,d_3)
d_1,d_2,d_3 = tmp_d_1,tmp_d_2,tmp_d_3
return max(d_2,d_3)
