123. Best Time to Buy and Sell Stock III Leetcode Java

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 at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

All relevant problems:

188. Best Time to Buy and Sell Stock IV 

123.Best Time to Buy and Sell Stock III

122. Best Time to Buy and Sell Stock II

121. Best Time to Buy and Sell Stock I

localMax[i][j]: The maximum profit on day i and must sell the stock on day i in j transactions.

globalMax[i][j]: The maximum profit on day i and must sell the stock before or on day i in j transactions.

This problem only allows two transactions. We use two arrays with size 2 to track the maximum local profit and maximum global profit on ith day. Clearly localMax[i][1]=Math.max(localMax[i-1][1]+prices[i]-prices[i-1], 0) as we discussed on problem 121. LocalMax[i][2]=Math.max(LocalMax[i-1][2]+ prices[i]-prices[i-1], globalMax[i][1]), so for two transactions, there are two possible trades that can make the maximum profit, one is to do almost the same trade as localMax[i-1][2] except for selling it on day i rather than day i-1. The other possible way is we have the global most profitable one time trade globalMax[i][1], so we conduct the first trade like that and then buy and sell the stock on the same day i, which make the profit= globalMax[i][1]. 

The reason is following:
localMax[i][2] must have 2 transactions, one is the globalMax[i][1](buy at lowest price prices[b1] and sell at highest price prices[s1]), the other one is buy at the lowest price(prices[b2]) after the day s1 (the day sell globalMax[i][1]) and sell on day i. localMax[i][2]= globalMax[i][1]+ prices[i]- prices[b2], but we don't know which day is b2 and we don't have to know. Because localMax[i-1][2] contains the information of b2. So basically we can get the localMax[i][2]=globalMax[i][1]+ prices[i]- prices[b2]=globalMax[i][1]+ prices[i-1]- prices[b2]+prices[i]-prices[i-1], Now we can see why there are two possibilities, if prices[i]<prices[b2], which means the prices[i] is the lowest prices after day s1 rather than b2, we'd better buy on day i and sell on day i to get maximum profit. 
localMax[i][2]:
if(prices[i]>prices[b2]): globalMax[i][1]+ prices[i-1]- prices[b2]+prices[i]-prices[i-1]=  LocalMax[i-1][2]+ prices[i]-prices[i-1]. b2 is preserved.
otherwise: globalMax[i][1]. b2 is updated to i.
Actually, for 1 transaction, we can assume globalMax[i][0]=0, that's how 1 transaction works in the general analysis.

Time complexity: O(n*k) 

 public int maxProfit(int[] prices) {  
     if(prices==null || prices.length<2) return 0;  
     int k=2;  
     int[] local=new int[k+1];
       int[] global=new int[k+1];
       for(int i=1;i<prices.length;i++){
           for(int j=1;j<=k;j++){
               local[j]=Math.max(local[j]+prices[i]-prices[i-1],global[j-1]);
               global[j]=Math.max(global[j],local[j]);
           }
       }
       return global[k]; 
   }