Best Time to Buy and Sell Stock with Cooldown

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

Approach - Bottom Up space optimized

• We have three states
  • Sold - today we sold
  • Hold - Today we bought
  • Rest - Today we did nothing aka rest day
• New sold is simply whatever prices we had when we bought and now add the prices simple
• hold needs max as it is possible last day we bought so hold already has that value or we bought today in that case we calculate
• For calculating rest it could be that last day was cooldown so rest would have the value or last day is when we bought in that case the rest value would be whatever we last sold on
• O(n), O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2)
            return 0;
 
        int hold = -prices[0], sold = 0, rest = 0;
        for (int i = 1; i < prices.length; i++) {
            int lastSold = sold;
            sold = hold + prices[i];
            hold = Math.max(hold, rest - prices[i]);
            rest = Math.max(rest, lastSold);
        }
 
        return Math.max(sold, rest);
    }
}

Approach - Bottom Up - 1D DP

• Simply compute the base case then for each sell day we go through all the previous day to find the buying day
• O(n^2) O(n)

class Solution {
    public int maxProfit(int[] prices) {
        if ( prices.length < 2)
            return 0;
 
        int[] dp = new int[prices.length];
        dp[1] = Math.max(prices[1]-prices[0],0); // base case
        for (int i = 2; i < prices.length; i++) { //sell
            dp[i] = dp[i-1]; // need to fill dp[i] for comparison later or you can say it is when we are doing nothing on day i
            for(int j = 0; j < i; j++) { //buy
                int prev_profit = (j >= 2) ? dp[j-2] : 0;
                int curr_profit = prev_profit + prices[i] - prices[j];
                dp[i] = Math.max(dp[i], curr_profit);
            }
        }
 
        return dp[prices.length - 1];
    }
}

Approach - Memoization

• We create a 2D DP for each day and 2 for either we buy or sell
• Similar step as every time if the solution already exist by checking for -1 then use that to save the time
• O(n), O(1) Check space maybe we create n variables eventually that’s why it could be n

class Solution {
    int[][] dp;;
    public int maxProfit(int[] prices) {
        dp = new int[prices.length+1][2];
        for(int[] n: dp)
            Arrays.fill(n,-1);
        return solve(prices, 0, 1);
    }
 
    int solve(int[] prices, int day, int buy) {
        if (day >= prices.length)
            return 0;
 
        if (dp[day][buy] != -1)
            return dp[day][buy];
 
        int profit = 0;
        if (buy == 1) {
            int take = solve(prices, day+1, 0) - prices[day];
            int notTake = solve(prices, day+1, 1);
            profit = Math.max(take, notTake);
        } else {
            int sell = prices[day] + solve(prices, day+2, 1);
            int notSell = solve(prices, day+1, 0);
            profit = Math.max(sell, notSell);
        }
 
        return dp[day][buy] = profit;
    }
}

Approach - Recursion

• So we have to create a tree and then transform to code
• If we are buying we have 2 options either to buy now or next day
• If we are selling we have 2 options either today or next day
• So we calculate based on that and find the profit
• For buying today we subtract the price and for selling today we would add
• O(2^n), O(1) Check space once

class Solution {
    public int maxProfit(int[] prices) {
        return solve(prices, 0, true);
    }
 
    int solve(int[] prices, int day, boolean buy) {
        if (day >= prices.length)
            return 0;
        int profit = 0;
        if (buy) {
            int take = solve(prices, day+1, false) - prices[day];
            int notTake = solve(prices, day+1, true);
            profit = Math.max(take, notTake);
        } else {
            int sell = prices[day] + solve(prices, day+2, true);
            int notSell = solve(prices, day+1, false);
            profit = Math.max(sell, notSell);
        }
 
        return profit;
    }
}