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