[C++] LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

题解

这是一道动态规划的题目，之前有过多道类似的题目。这里增加了冷冻期，不能进行交易。那么第

i

天之前最后一次有三种状态，即：买入，卖出，冷冻期。

那么第

i

天的时候一共有三种选择，买入、卖出和冷冻期，由于冷冻期可以看成和第

i-1

操作一样，故可以不用考虑，因此这里只需要考虑买入和卖出两种状态。维护两个数组

sell

和

buy

，其中

sell

表示最后一次操作是卖出的最大利润，

buy

表示最后一次是买入的最大利润。

那么状态转移方程如下：

sell[i]=max(sell[i-1],buy[i-1]+prices[i]

buy[i]=max(buy[i-1],sell[i-2]-prices[i]

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<2) return 0;
        vector<int> buy(n,0),sell(n,0);
        buy[0]=0-prices[0];sell[0]=0;
        for(int i=1;i<n;i++){
            if(i==1)
                buy[i]=max(buy[i-1],0-prices[i]);
            else
                buy[i]=max(buy[i-1],sell[i-2]-prices[i]);
            sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
        }
        return sell[n-1];
    }
};