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: prices={1,2,3,0,2}
Output: 3 

Approach

Java

public class BuySellStockWithCooldown {
    public static void main(String[] args) {
        int[] prices = { 1, 2, 3, 0, 2 };
        System.out.println(maxProfit(prices));
    }

    static int maxProfit(int[] prices, int f, int day, int[][] dp) {
        // base case
        if (day >= prices.length)
            return 0;

        // if already calculated
        if (dp[f][day] != 0)
            return dp[f][day];

        // if f is false
        if (f == 0) {

            int x = maxProfit(prices, (f == 0 ? 1 : 0), day + 1, dp) - prices[day];
            int y = maxProfit(prices, f, day + 1, dp);
            dp[f][day] = Math.max(x, y);
        }
        // ele
        else {
            int x = prices[day] + maxProfit(prices, (f == 0 ? 1 : 0), day + 2, dp);
            int y = maxProfit(prices, f, day + 1, dp);
            dp[f][day] = Math.max(x, y);
        }
        return dp[f][day];
    }

    static int maxProfit(int[] prices) {
        int dp[][] = new int[2][prices.length];
        return maxProfit(prices, 0, 0, dp);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


int maxProfit(vector<int>&prices,bool f,int day,
      vector<vector<int>>&dp)
{
    //base case
    if(day>=prices.size())
            return 0;

    //if already calculated
    if(dp[f][day]!=-1)
          return dp[f][day];

    //if f is false
    if(!f)
      {
           
            int x = maxProfit(prices,!f,day+1,dp) - prices[day];
            int y = maxProfit(prices,f,day+1,dp);
             dp[f][day] = max(x,y);
       }
    //ele
    else
        {
            int x  = prices[day] + maxProfit(prices,!f,day+2,dp);
            int y  = maxProfit(prices,f,day+1,dp);
       dp[f][day] = max(x,y);}
        return dp[f][day];
}

int maxProfit(vector<int>& prices)
{
        vector<vector<int>>dp(2,vector<int>(prices.size(),-1));
        return maxProfit(prices,false,0,dp);
}

int main()
{
   vector<int> prices= {1,2,3,0,2};
   cout<<maxProfit(prices);
   return 0;
}