# 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:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

# Solution

Approach 1: DP with two tables - O(n) time.

Approach 2: DP - O(n^2) time.

# Code (Python)

Approach 1:

    def maxProfit(self, prices: List[int]) -> int:
        # idea: buy and sell are separate actions now, and the previous action affects the next action
        # therefore we need 2 separate tables to store max profit when you have or don't have the stock at the end of the day
        if len(prices) < 2:
            return 0
        
        # hold: max profit at end of day i if still holding the stock
        hold = [-prices[0], max(-prices[0], -prices[1])] + [0] * (len(prices) - 2)
        # sold: max profit at end of day i if you don't own the stock
        sold = [0, max(0, prices[1] - prices[0])] + [0] * (len(prices) - 2)
        
        for i in range(2, len(prices)):
            # if own stock today, either still hold yesterday's stock, or buy it in
            hold[i] = max(hold[i-1], sold[i-2] - prices[i])
            # if don't own stock today, either still don't have it yesterday, or just sold it today
            sold[i] = max(sold[i-1], hold[i-1] + prices[i])
        
        return sold[-1]

# Code (C++)

Approach 1:

// DP - O(n).
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1)
            return 0;
        int buy1 = 0;
        int buy2 = 0 - prices[0];
        int sell1 = 0;
        int sell2 = 0;
        for (int i = 1; i < n; ++i)
        {
            int buy3 = std::max(buy2, sell1 - prices[i]);
            int sell3 = std::max(sell2, buy2 + prices[i]);
            buy2 = buy3;
            sell1 = sell2;
            sell2 = sell3;
        }
        return sell2;
    }
};

// DP - O(n).
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1)
            return 0;
        int buy1 = 0 - prices[0];
        int buy2 = std::max(buy1, 0 - prices[1]);
        int sell1 = 0;
        int sell2 = std::max(sell1, buy1 + prices[1]);
        for (int i = 2; i < n; ++i)
        {
            int buy3 = std::max(buy2, sell1 - prices[i]);
            int sell3 = std::max(sell2, buy2 + prices[i]);
            buy2 = buy3;
            sell1 = sell2;
            sell2 = sell3;
        }
        return sell2;
    }
};

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

Approach 2:

// DP - O(n^2).
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1)
            return 0;
        vector<int> head = vector<int>(n, 0);
        for (int i = n - 2; i >= 0; --i)
        {
            head[i] = head[i+1];
            for (int j = i + 1; j < n; ++j)
            {
                int tmp = prices[j] - prices[i];
                if (j < n - 2)
                    tmp += head[j+2];
                head[i] = std::max(head[i], tmp);
            }
        }
        return head[0];
    }
};

// DP - O(n^2).
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1)
            return 0;
        vector<int> tail = vector<int>(n, 0);
        for (int i = 1; i < n; ++i)
        {
            tail[i] = tail[i-1];
            for (int j = i - 1; j >= 0; --j)
            {
                int tmp = prices[i] - prices[j];
                if (j > 1)
                    tmp += tail[j-2];
                tail[i] = std::max(tail[i], tmp);
            }
        }
        return tail[n-1];
    }
};