309. Best Time to Buy and Sell S

Share my thinking process

典型dp，问题的关键在于找到一个变量来表示不同的状态以及推演出状态转移方程

这道题目有3种可能的状态，buy，sell，rest，其中rest表示冷冻期。
借助3个辅助数组buy[i],sell[i],rest[i]：
buy[i]：表示第i天前，任何以buy状态结尾的交易序列所获得的最大利润
sell[i]：表示第i天前，任何以sell状态结尾的交易序列所获得的最大利润
rest[i]：表示第i天前，任何以rest状态结尾的交易序列所获得的最大利润

我们需要得到这3个状态的转移方程，通过推算，可以得出以下3条结论：

buy[i]  = max(rest[i-1]-price, buy[i-1]) 
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

解释:
1.对于buy[i]，表示第i天前以buy结尾的交易所获得的最大收益。
那么第i天有两种状态，1.buy(买) 2.rest(观察)
当第i天选择购买的时候，此时buy[i] = rest[i-1] -price （购买之前必须经历冷冻期）
当第i天选择不买的时候，根据buy[i]的定义， buy[i] = buy[i-1]，此时的收益就是第i-1天前以buy结尾的交易所获得的最大收益

2.sell同理。

细节：1.rest必须出现在buy之前  2.buy必须出现在sell之后

如何确保，排除 buy rest buy 的情况

答案在这里：buy[i] <= rest[i] 推出 rest[i]=max(sell[i-1],rest[i-1])
这避免了buy rest buy 的情况
同时： sell[i] >= rest[i] 推出 rest[i] = sell[i-1]

通过上面3条状态转移方程，可能出现的情况为:
1.rest buy (i天买)
   buy rest

2.sell rest
   buy rest sell(i天卖）

3.buy rest    (这条➕1.i天买， 会出现 buy rest buy)
   sell rest
   rest rest

将结论代入 buy[i] 可以将3条状态转移方程优化为2条
buy[i] = max{buy[i-1],sell[i-2]-price}
sell[i] = max{sell[i-1],buy[i-1]+price}

但是还可以优化的更好：通过观察得出第i天的最大收益，只与i-1,i-2天有关。其中sell[i-2] = sell[i-1]。可以将O(n)的空间复杂度转化为O(1)

public int maxProfit(int[] prices) {
    int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
    for (int price : prices) {
        prev_buy = buy;
        buy = Math.max(prev_sell - price, prev_buy);
        prev_sell = sell;
        sell = Math.max(prev_buy + price, prev_sell);
    }
    return sell;
}