leetcode-buy-stocks-cooldown

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

　　leetcode买卖股票系列问题之一，不限次买入和卖出，但要求必须在卖出之后才能买入，另外买入和卖出之间至少间隔一个冷却天数。

题目分析

　　思路参考了这里：

　　https://discuss.leetcode.com/topic/30421/share-my-thinking-process/9

　　我们用两个数组sell和buy代表状态，sell[i]的含义是，第i 天之前包括第i天的所有以sell为结尾的序列所能得到的最大收益。buy[i]的含义是第i 天之前包括第i天的所有以buy为结尾的序列所能得到的最大收益。price[i]表示当天股票价格。leetcode的discuss区里有人还用了有限状态自动机画图直观的表示了出来sell，buy，cooldown三者转移关系，实际上，只需要两个数组保存状态就可以。

1
2
sell[i] = max(sell[i - 1], buy[i－1] + price[i]);
buy[i] = max(buy[i - 1], sell[i - 2] - price[i]);

　　有了转移方程以后，代码就比较好写了。注意一下sell[i]和buy[i]都依赖于前一项或者前两项的值，因此不需要保存所有的sell和buy值，额外空间复杂度为O(1)。但要注意buy初值设置成负数最小值，sell初值设置为0即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
    //buy[i] = max(sell[i-2]-price, buy[i-1])
    //sell[i] = max(buy[i-1]+price, sell[i-1])
    int buy = Integer.MIN_VALUE; //buy代表前一项buy值
    int prev_sell = 0; //pre_sell代表前前项的sell值
    int sell = 0; //sell代表前项的sell值
    for(int price : prices) {
        int prev_buy = buy;
        buy = Math.max(buy, prev_sell - price);
        prev_sell = sell;
        sell = Math.max(prev_buy + price, sell);
    }
    return sell;
}