6.Best Time to Buy and Sell Stock with Cooldown

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)

Solution:

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        if (prices.size() == 0 || prices.size() == 1)
        {
            return 0;
        }

        int noStockPrev = 0;
        int soldPrev = 0;
        int inHandPrev = -prices[0];

        for (int i = 1; i < prices.size(); i++)
        {

            int noStock = max(noStockPrev, soldPrev);
            int sold = inHandPrev + prices[i];
            int inHand = max(inHandPrev, (noStockPrev - prices[i]));

            noStockPrev = noStock;
            soldPrev = sold;
            inHandPrev = inHand;
        }

        return max(noStockPrev, soldPrev);
    }
};

Time Complexity: O(n)