309. Best Time to Buy and Sell Stock with Cooldown -M !!!!!!!!!!!!!!!!!!!!!!!!!

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:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

A:

--------------------这是我的解法，结果是错的。肏~~~~~~~~~~~~~~

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int total = 0;  // withouth cooldown
        for(int i =1;i<n;++i)
        {
            if(prices[i] > prices[i-1])
                total+= prices[i] - prices[i-1];
        }
        for(int i =2; i<n-1; ++i)
        {
            if(prices[i-1] > prices[i-2]  and prices[i] < prices[i+1])
            {
                total -= min( prices[i-1] - prices[i-2], prices[i+1] - prices[i] );
            }
        }
        // Above, would fail for [1,3,2,4,7]
        return total;
    }
};

-------------------------上面修改后的的版本,其实也不行，因为没有前面用或者不用，会影响后面的up -> down -> up 的情况---------------------

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int total = 0;  // withouth cooldown
        for(int i =1;i<n;++i)
        {
            if(prices[i] > prices[i-1])
                total+= prices[i] - prices[i-1];
        }
        for(int i =2; i<n-1; ++i)
        {
            //  i-2 go up to i-1, i-1 go down i, i go up i+1
            if(prices[i] < prices[i-1] and prices[i-1] > prices[i-2]  and prices[i] < prices[i+1])
            {
                int lastEndingProfit = prices[i-1] - prices[i-2];
                int nextBegingProfit = prices[i+1] - prices[i];
                                                            
                int sellAndBuyExtraProfit = min( lastEndingProfit, nextBegingProfit );
                // if no sell and no buy, 
                // i.e.  ignore the  process, we directly from i-2 to i+1
                int noBuyNoSellProfit =   prices[i+1] - prices[i-2]; // profit from A to D
                int noBuyNoSellExtraProfit = lastEndingProfit + nextBegingProfit -noBuyNoSellProfit;
                total -= min(sellAndBuyExtraProfit, noBuyNoSellExtraProfit );
            }
        }
        return total;
    }
};

---------------状态转移  。  只不过，我们之前的都是2个状态，现在是3个了-----------------

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int lastBuy = INT_MIN/2, lastCool = 0, lastSell = 0; // status-wise maximum profit 
        for(int v : prices)
        {
            int newBuy = max(lastCool - v, lastBuy);// either use previous buy, and buy this time
            int newCool = max(lastCool, lastSell);
            int newSell = lastBuy + v;
            
            lastSell = newSell;
            lastCool = newCool;
            lastBuy = newBuy;
        }
        return max(lastSell, lastCool);
    }
};

--------------利用状态图------------------------

// Author: Huahua
// Running time: 12 ms
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sold = 0;
        int rest = 0;
        int hold = INT_MIN;
        for (const int price : prices) {
            int prev_sold = sold;
            sold = hold + price;
            hold = max(hold, rest - price);
            rest = max(rest, prev_sold);
        }
        return max(rest, sold);
    }
};

Mistakes: