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).

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= prices.length &lt;= 5000
	0 &lt;= prices[i] &lt;= 1000


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        
        cache = {}
        def dfs(i, buying):
            
            if i >= len(prices):
                return 0
            
            if (i, buying) in cache:
                return cache[(i, buying)]
            
            if buying:
                # if have sell the share in previous step
                # then currently we have two options
                # either buy or not buy(cooldown)
                
                # we have bought so, increment the index and set buying flag to not buying
                # and don't forget that we bought so, we have to reduce that share amount from profit
                buy = dfs(i+1, not buying) - prices[i] 
                
                cooldown = dfs(i+1, buying)
                
                profit = max( buy, cooldown )
                cache[(i, buying)] = profit
                
            else:
                # we have sell the share so, 
                # we cannot buy next share we have to skip the next price(cooldown for one day)
                # set (not buying) flag to buying
                # we also have to add that share price to profit
                sell = dfs(i+2, not buying) + prices[i] 
                
                cooldown = dfs(i+1, buying)
                
                profit = max( sell, cooldown )
                cache[(i, buying)] = profit
                
            return cache[(i,  buying)]
        
        return dfs(0, True)
class Solution {
    public int maxProfit(int[] prices) {

        int n = prices.length;

        int[][] dp = new int[n+2][2];

        for(int index = n-1; index>=0; index--){
            for(int buy = 0; buy<=1; buy++){

                int profit = 0;

                if(buy == 0){ // buy stocks
                    profit = Math.max(-prices[index] + dp[index+1][1], 0 + dp[index+1][0]);
                }
                if(buy == 1){ // we can sell stocks
                    profit = Math.max(prices[index] + dp[index+2][0], 0 + dp[index+1][1]);
                }
                dp[index][buy] = profit;
            }
        }
        return dp[0][0];
    }
}
class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int ans = 0;
    vector<int> dp(n, 0);
    for (int i = 1; i < n; ++i) {
      int max_dp = 0;
      for (int j = 0; j < i; ++j) {
        dp[i] = max(dp[i], prices[i] - prices[j] + max_dp);
        max_dp = max(max_dp, j > 0 ? dp[j - 1] : 0);
      }
      ans = max(ans, dp[i]);
    }
    return ans;
  }
};
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let dp = {};
    let recursiveProfit = (index,buy) =>{
        if(index>=prices.length){
            return 0;
        }
        if(dp[index+'_'+buy]) return dp[index+'_'+buy]
        if(buy){
            dp[index+'_'+buy] = Math.max(-prices[index]+recursiveProfit(index+1,0), 0+recursiveProfit(index+1,1))
            return dp[index+'_'+buy];
        }
        else{
            dp[index+'_'+buy]= Math.max(prices[index]+recursiveProfit(index+2,1),0+recursiveProfit(index+1,0))
            return dp[index+'_'+buy];
        }
    }
    return recursiveProfit(0,1);
};
Best Time to Buy and Sell Stock with Cooldown