1 /**
  2      * Design an algorithm to find the maximum profit. You may complete at most two transactions.
  3      * @param prices
  4      * @return
  5      */
  6     public int maxProfit3(int[] prices){
  7         if(prices==null || prices.length <= 1)
  8             return 0;
  9         int profit = 0;
 10         int len = prices.length;
 11         //the local minimum is marked as -1;the local maximum is marked as 1; otherwise is 0
 12         int[] mark = new int[len];
 13         int[] left = new int[len];//mark whether the left is <= or >=
 14         int[] right = new int[len];//mark whether the right is <= or >=
 15         // the first number is initialized as 0
 16         left[0] = 0;
 17         //get the left array, by one traversal
 18         int i=1;
 19         while(i<len){
 20             if(prices[i-1]<prices[i])
 21                 left[i] = -1;
 22             else if(prices[i-1]>prices[i])
 23                 left[i] = 1;
 24             else
 25                 left[i] = left[i-1];
 26             i++;
 27         }
 28         //initialize the last element 
 29         right[len-1] = 0;
 30         i = len-2;
 31         while(i>=0){
 32             if(prices[i+1]<prices[i])
 33                 right[i] = -1;
 34             else if(prices[i+1]>prices[i])
 35                 right[i] = 1;
 36             else
 37                 right[i] = right[i+1];
 38             i--;
 39         }
 40         //get the mark
 41         i = 0;
 42         while(i<len){
 43             if(left[i] == right[i]){
 44                 mark[i] = left[i]*(-1);
 45             }else {
 46                 if(left[i] == 0){
 47                     mark[i] = right[i]*(-1);
 48                 }
 49                 else if(right[i] == 0)
 50                         mark[i] = left[i]*(-1);
 51                 else
 52                     mark[i] = 0;
 53             }
 54             i++;
 55         }
 56         for( i=0;i<len-1;i++){
 57             if(mark[i] == 1){
 58                 int temp1 = oneTransaction(0, i+1, prices);
 59                 int temp2=0;
 60                 if(i+1<len)
 61                     temp2 = oneTransaction(i+1,len,prices);
 62                 if(temp1+temp2>profit)
 63                     profit = temp1+temp2;
 64             }
 65         }
 66         int temp = oneTransaction(0,len,prices);
 67         if(temp>profit)
 68             profit = temp;
 69         return profit;
 70     }
 71     /**
 72      * 
 73      * @param start [
 74      * @param end ）
 75      * @param mark
 76      * @param prices
 77      * @return
 78      */
 79     private int oneTransaction(int start, int end,  int[] prices){
 80        if(end-start<=1)
 81            return 0;
 82        if(end-start==2)
 83            return prices[end-1]-prices[start]>0?prices[end-1]-prices[start]:0;
 84         int len = prices.length;
 85         int[] lmin = new int[len];
 86         int[] rmax = new int[len];
 87         lmin[start] = prices[start];
 88         int i = start+1;
 89         while(i<end){
 90             if(prices[i]>lmin[i-1])
 91                 lmin[i] = lmin[i-1];
 92             else
 93                 lmin[i] = prices[i];
 94             i++;
 95         }
 96         i = end-1;
 97         rmax[i] = prices[i];
 98         i--;
 99         while(i>=start){
100             if(prices[i]>rmax[i+1])
101                 rmax[i] = prices[i];
102             else
103                 rmax[i] = rmax[i+1];
104             i--;
105         }
106         int max = 0;
107         for(i=start;i<end;i++){
108             if(rmax[i]-lmin[i]>max)
109                 max = rmax[i] - lmin[i];
110         }
111         return max;
112     }
113