Today’s Leetcode July Challenge, Best Time to Buy and Sell Stock with Cooldown, is a variation of the more typical problem of maximizing profit by sequentially buying and selling an array of stocks–either once or multiple times depending on the minor variant. What the challenge problem adds is a requirement that after a stock is sold there is a one day cooldown during which no buying or selling is allowed. To better understand that, let’s look at a very simple example where the cooldown is effect.

Input: [2,3,4,1,3] Max Profit: 4
        b   s b s Optimal buy-sell without cooldown.

Input: [2,3,4,1,3] Max Profit: 3
        b s   b s Optimal buy-sell with cooldown.

int maxProfit(vector<int>& prices) {
   int n = prices.size();
   if(n < 2) return 0;
   
   int holdingStockProfit[n];
   int notHoldingStockProfit[n];
   
   // BASE CASES
   // day 0
   holdingStockProfit[0] = -prices[0];
   notHoldingStockProfit[0] = 0;
   
   // day 1
   holdingStockProfit[1] = 
	   max(holdingStockProfit[0], notHoldingStockProfit[0]-prices[1]);
   notHoldingStockProfit[1] = 
	   max(notHoldingStockProfit[0], holdingStockProfit[0] + prices[1]);
   
   for(int day=2;day<n;day++) {
	  holdingStockProfit[day] = 
		  max(holdingStockProfit[day-1], notHoldingStockProfit[day-2] - prices[day]);
	  notHoldingStockProfit[day] = 
		  max(notHoldingStockProfit[day-1], holdingStockProfit[day-1] + prices[day]);
   }
   
   return notHoldingStockProfit[n-1];
}

int maxProfit(vector<int>& prices) {
   int days = prices.size();
   if(days < 2) return 0;
   
   int profit[days][2];
   
   // BASE CASES
   // day 0
   profit[0][buying] = -prices[0];
   profit[0][selling] = 0;
   
   // day 1
   profit[1][buying] = max(profit[0][buying], profit[0][selling] - prices[1]);
   profit[1][selling] = max(profit[0][selling], profit[0][buying] + prices[1]);
   
   for(int day=2;day<days;day++) {
	  profit[day][buying] = 
		  max(profit[day-1][buying], profit[day-2][selling] - prices[day]);
	  profit[day][selling] = 
		  max(profit[day-1][selling], profit[day-1][buying] + prices[day]);
   }
   
   return profit[days-1][selling];
}

int maxProfit(vector<int>& prices) {
   if(prices.size() < 2) return 0;

   int buying = -prices[0];
   int selling = 0;
   int cooldown = 0;
   int minustwo;
   
   for(auto price : prices) {
	  minustwo = cooldown;
	  cooldown = selling;
	  selling = max(selling, buying + price);
	  buying = max(buying, minustwo - price);
   }
   return selling;
}