Best Time to Buy and Sell Stock III !!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Q:
Say you have an array for which the i^th 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).
 
A:    算法2更好， 在最下面

------------------------3 rd pass -------------------
以前脑子不清醒。  这个明明就是2次分开的profit的情况。
也就是说，可以先找出最赚钱的那个情况，然后，再 找出左右两边的subarray中最赚钱的情况。然后二者相加即可。



嗯，还是算法2， 左右扫，更好些。


divide and conquer
设i从0到n-1，那么针对每一个i，看看在prices的子序列[0,...,i][i+1,...,n-1]上分别取得的最大利润（第一题）即可。
这样初步一算，时间复杂度是O(n²)。

经过和只买一次的情况对比，我们发现：
Idea:
分两种情况：
1： 第二个max和只有一个transaction时的数组（max1）  分离的。
              最新的一遍，只考虑了这一种情况，大谬 ！！！！！！！！
2： max2与 max1有交际-----

public class Solution {
   
    public static final int minValue = -100000;

    public int maxProfit(int[] prices) {
        // This is max profit for two transactions
        if (prices != null && prices.length <= 1) {
            return 0;
        }
        int[] change = new int[prices.length - 1];
        for (int i = 0; i < prices.length - 1; i++) {
            change[i] = prices[i + 1] - prices[i];
        }
        // return maxChange(change, 0, change.length - 1)[2];
        // case 1:
        // when the 2nd transaction independent of the 1st transaction
        // i.e. they are disjoint
        int[] max1 = maxChange(change, 0, change.length - 1);
        // exclude the intervals from changes , to do second max
        if(max1[2]<0){
            return 0; // if the max buying profit in a single transaction is < 0
        }

        int[] modifiedChanges = new int[change.length];
        for (int i = 0; i < change.length; i++) {
            if (i >= max1[0] && i <= max1[1]) {
                modifiedChanges[i] = minValue;
            } else {
                modifiedChanges[i] = change[i];
            }
        }
        int[] max2 = maxChange(modifiedChanges, 0, change.length - 1);
        //since when change = [1] only, the max 2 would return the above min_value;
        int disJointMax = max1[2] + Math.max( max2[2],0); // we can reasonbalely assume that max2[2]>0

        // Case 2:
        // when two transactions are both intersect with the interval of one
        // transaction
        // we know that left and right terminal belongs to the two transactions.
        // but they finally divided by the negative interval inside max1
        // First we modify the changes.
        for (int i = 0; i < change.length; i++) {
            modifiedChanges[i] = -change[i];
        }

        int[] minInside = maxChange(modifiedChanges, max1[0], max1[1]);

        if (minInside[0] - 1 < 0 || minInside[1] + 1 > change.length - 1) { 
            // actually this is the case 1
            return disJointMax;
        }
        int[] maxLeft = maxChange(change, 0, minInside[0] - 1);
        int[] maxRight = maxChange(change, minInside[1] + 1, change.length - 1);

        int intersectMax = maxLeft[2] + maxRight[2];
        if (disJointMax > intersectMax) {
            return Math.max(disJointMax, 0);
        } else {
            return Math.max(intersectMax, 0);
        }
    }

    // divide and conquere problem.
    public int[] maxChange(int[] change, int start, int end) {
        if (start == end) {
            int[] tmp = { start, end, change[start] };
            return tmp;
        } else {
            int middle = (int) ((start + end) / 2);
            int[] leftMax = maxChange(change, start, middle);
            int[] rightMax = maxChange(change, middle + 1, end);
            int[] crossMax = maxCross(change, start, middle, end);

            if (leftMax[2] >= rightMax[2] && leftMax[2] >= crossMax[2])
                return leftMax;
            if (rightMax[2] >= leftMax[2] && rightMax[2] >= crossMax[2])
                return rightMax;
            else
                // (crossMax[2] >= leftMax[2] && crossMax[2] >= rightMax[2])
                return crossMax;
        }

    }

    private int[] maxCross(int[] change, int start, int middle, int end) {
        // get max left part
        int leftMax = 0;
        int sum = 0;
        int leftIndex = middle;
        for (int i = middle; i >= start; i--) {
            sum += change[i];
            if (sum > leftMax) {
                leftMax = sum;
                leftIndex = i;
            }
        }
        int rightMax = 0;
        int rightIndex = middle + 1;
        sum = 0;
        for (int i = middle + 1; i <= end; i++) {
            sum += change[i];
            if (sum > rightMax) {
                rightMax = sum;
                rightIndex = i;
            }
        }
        int[] tmp = { leftIndex, rightIndex, leftMax + rightMax };
        return tmp;
    }
}

Mistakes:
1： 没有考虑，可以有不买的选择，因此，当price =[2,1]时，输出了-1，而不是0.




Learned:
1:上面犯了一个错误。
原因在于，java的最小最大值如何运算，没搞清楚。看下面

  System.out.println(Integer.MIN_VALUE);
  System.out.println(Integer.MIN_VALUE-1);
打印的结果为：  
-2147483648
2147483647

---------------------------第二遍， 有新解法----------------------------
思路来源于 这里
哎，其实，本题目的题意是这样的：
某一天买进， 再后面的一天卖出，这样就是利润。
 因此，也只需要， 找到前面的一天最low的， 再找到后面的一天最high的 ， 就可以了。
问题1，之所以要用divide and conquere ，就是解决O(n)的问题，而且用了O(lg(n))的空间复杂度。

现在，我们放开， 就可以用O(n)的空间复杂度+ 时间复杂度 解决问题1.。。 DP思想。
那么，本问题III， 也可以用 类似的思想解决。
 

改进的方法就是动态规划了，那就是第一步扫描，先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。
第二步是逆向扫描，计算子序列[i,...,n-1]上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。

public class Solution { 
    public int maxProfit(int[] prices) {
        if(prices.length <= 1 )
            return 0;
        int n = prices.length, minBefore = prices[0];
        int maxProfitBefore[] = new int[n];
        for(int i =1;i<n;i++){
            maxProfitBefore[i] = Math.max(maxProfitBefore[i-1],prices[i] - minBefore);
            minBefore = Math.min(minBefore, prices[i] );
        }
        // calculate last 
        int result = 0, maxAfter = prices[n-1];
        for(int i=n-2;i>=0;i--){
            result = Math.max(result, maxProfitBefore[i] + maxAfter - prices[i]);
            maxAfter = Math.max(maxAfter, prices[i]);
        }
        return result;
    }
}