[动态规划] leetcode 309 Best Time to Buy and Sell Stock with Cooldown

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]);
    }
};

 

上一篇:vim简单题练习-------出自《鸟哥的linux私房菜》第309页码题目


下一篇:LeetCode 309. 最佳买卖股票时机含冷冻期