problem:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
这道题有好几个变种。对于没有cooldown的题目而言,只需要考虑第i天,当前持有股票的最大收益和当前不持有股票的最大收益。而引入cooldown后,我们也需要引入新的状态:
hasStock : 记录当天持有股票时的最大收益:可能是之前就有的,也可能是当天买的(由于必须是冷却一天才能买新的股票,需要从冷却状态转换过来),取两者的最大值。
cool:记录当天的操作选择冷却时的最大收益,可以选择一直冷却,也可以刚卖完股票进入冷却;取两者的最大值。
sell:记录当天选择出售股票后的收益。
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); vector<int> hasStock(n + 1, -500000); vector<int> sell(n + 1, -500000); vector<int> cool(n + 1, 0); int res = 0; for(int i = 0;i < n;i++) { hasStock[i + 1] = max(hasStock[i], cool[i] - prices[i]); cool[i + 1] = max(sell[i], cool[i]); sell[i + 1] = hasStock[i] + prices[i]; } return max(cool[n], sell[n]); } };