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

public class Solution {
    public int maxProfit(int[] prices) {
    	if(prices.length < 2){
    		return 0 ;
    	}
 		int[] profit = new int[prices.length];
 		int tmpProfit = 0;
 		int min = Integer.MAX_VALUE;

 		for(int i = 0; i < prices.length; i++){
 			if(min > prices[i]){
 				min = prices[i];
 			}
 			if(tmpProfit < prices[i] - min){
 				tmpProfit = prices[i] - min;
 			}
 			profit[i] = tmpProfit;
 		}       

 		int max = Integer.MIN_VALUE;
 		int[] profitBack = new int[prices.length];
 		tmpProfit = 0;

 		for(int i = prices.length - 1; i >= 0; i--){
 			if(max < prices[i]){
 				max = prices[i];
 			}

 			if(tmpProfit < max - prices[i]){
 				tmpProfit = max - prices[i];
 			}

 			profitBack[i] = tmpProfit;
 		}

 		int res = tmpProfit;

 		for(int i = prices.length - 1; i >= 1; i--){
 			if(profitBack[i] + profit[i - 1] >= res){
 				res = profitBack[i] + profit[i - 1];
 			}
 		}
 		// for(int i = 1; i < prices.length; i++){
 		// 	if(profit[i] + profitBack[i + 1] > res){
 		// 		res = profit[i] + profitBack[i + 1];
 		// 	}
 		// }

 		return res;
    }
}
@@ -1398,8 +1398,838 @@
 %0A    %7D%0A%7D
+%0A%0A%0Apublic class Solution %7B%0A    public int maxProfit(int%5B%5D prices) %7B%0A    %09int len = prices.length;%0A    %09if (len == 0) %7B%0A    %09%09return 0;%0A    %09%7D%0A%0A    %09int%5B%5D leftProfit = new int%5Blen%5D;%0A    %09int min = prices%5B0%5D;%0A    %09int tempProfit = 0;%0A%0A    %09for (int i = 1; i %3C len; i++) %7B%0A    %09%09min = min %3C prices%5Bi%5D? min : prices%5Bi%5D;%0A    %09%09tempProfit = tempProfit %3E (prices%5Bi%5D - min)? tempProfit : (prices%5Bi%5D - min);%0A    %09%09leftProfit%5Bi%5D = tempProfit;%0A    %09%7D%0A%0A    %09int globalMax = 0;%0A    %09tempProfit = 0;%0A    %09int max = prices%5Blen - 1%5D;%0A%0A    %09for (int i = len - 2; i %3E= 0; i--) %7B%0A    %09%09max = max %3E prices%5Bi%5D? max : prices%5Bi%5D;%0A    %09%09tempProfit = tempProfit %3E (max - prices%5Bi%5D)? tempProfit : (max - prices%5Bi%5D);%0A    %09%09globalMax = globalMax %3E (tempProfit + leftProfit%5Bi%5D)? globalMax : (tempProfit + leftProfit%5Bi%5D);%0A    %09%7D%0A%0A    %09return globalMax;%0A    %7D%0A%7D

update best time to buy and sell sotck iii solution;