309. Best Time to Buy and Sell Stock with Cooldown

题目如下：

Say you have an array for whichthe ith elementis the price of a given stock on day i.

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

·        Youmay not engage in multiple transactions at the same time (i.e, you must sellthe stock before you buy again).

·        Afteryou sell your stock, you cannot buy stock on next day. (i.e, cooldown 1 day)

Example:

Input: [1,2,3,0,2]

Output: 3 

Explanation: transactions = [buy, sell, cooldown, buy, sell]

此题有一个简化版本，为题目121.Best Time to Buy and Sell Stock，去掉了cooldown规则2，即只允许买卖一次。

有O(N)解法如下：

classSolution {
public:
       intmaxProfit(vector<int>& prices)
       {
              intbuy = INT_MAX;
              intsell = 0;
              for(int i = 0; i < prices.size(); i++)
              {
                     buy= min(buy, prices[i]);
                     sell= max(sell, prices[i] - buy);
              }
              returnsell;
       }

};

再做此题，第一个想法是考虑不同买卖的次数 i（即将vector prices分成i段），再调用上述maxProfit函数即可，但发现这么做不好确定如何进行分段（穷搜复杂度太高），只能作罢。

LeetCode上的高票答案，转自答主npvinhphat，无授权:）

这个图实在是太丑了:)

3个状态S0,S1,S2,S0表示尚未买进时，S1表示买进尚未卖出时，S2表示卖出后。

在每一个时刻i，使用S0[i],s1[i],s2[i]分别表示i时刻的利润，则3个状态之间的转换关系如下：

s0[i] = max(s0[i - 1], s2[i - 1]); // i-1时刻处于S0状态，并且i时刻未买入(cooldown中) 或者 i-1时刻处于S2状态，经过i时刻cooldown后进入S0状态

s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // 前一时刻买入，即由S0转入S1,或者前一时刻已经买入，i时刻cooldown

s2[i] = s1[i - 1] + prices[i]; // 只能从i-1时刻处于S1状态并且卖出转化得到

利润的最大值显然从最后时刻S0序列或者S2序列得到，S1序列尚有货物未卖出。

定义初始条件:

s0[0] = 0; // 若0时刻选择cooldown，则利润为0

s1[0] = -prices[0]; // S1时刻买入，此时尚未卖出，利润为负数

s2[0] = 0; // 0时刻不可能处于该状态，答主把和这个初始值定义为最大值，我觉得有点问题，改成了0

Here is the code :D

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