309. 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:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

Solution:

State machine.

In each day, there are only three possible states: bought a share, sold a share,cooling down.

There are several rules for those operations:

You must buy a share before you sell a share. 

You can only buy a share after a cool down day.

The maximum profit must happen when you sell the share. 

So we can use 3 variables to track maximum profits for all possible ending operations until day i (the operation is not necessary happens exactly at day i except cooldown. Cooldown keeps track the maximum profit at day i if we cooldown at day i). 

prices = [1, 2, 3, 0, 2]

For day 0,

Obviously, maxBuy[0] is -1, maxSell[0] is 0 because you have to buy it before you can sell it. maxCool[0] should be 0 as well, because it means you don't do anything on day 0.

For day 1.

Obviously, maxBuy at this day would be the previous maxCool-prices[1] for following reasons: 

a. You can't buy after a sell you have to wait after cooldown.

b. Definitely it produce more profit to buy after cooldown compare buy a share after buying.

maxBuy[1]  =Math.max(maxBuy[0],maxCool[0]-prices[1])=-1;

maxSell[1] should be Math.max(maxSell[0], maxBuy[0]+prices[1] )=1;

maxCool[1]=Math.max(maxBuy[0],maxSell[0])=0;

For day 2:

maxBuy[2]  =Math.max(maxBuy[1],maxCool[1]-prices[2])=-1;

maxSell[2] should be Math.max(maxSell[1], maxBuy[1]+prices[2] )=2;

maxCool[2]=Math.max(maxBuy[1],maxSell[1])=1;

We can keep going during 1 pass and return the maxSell at the end.

  public int maxProfit(int[] prices) {  
     if(prices==null|| prices.length==0) return 0;  
     int maxBuy=-prices[0];  
     int maxSell=0;  
     int maxCool=0;  
     for(int i=1;i<prices.length;i++){  
       int a=maxBuy;  
       int b=maxSell;  
       maxSell=Math.max(maxSell,maxBuy+prices[i]);  
       maxBuy=Math.max(maxBuy,maxCool-prices[i]);  
       maxCool=Math.max(a,b);  
     }  
     return maxSell;  
   }