Best Time to Buy and Sell Stock III

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

In this case, we can only buy and sell stock at most twice and you can only hold one stock at a given time.

So we divide the array into to parts, each transaction will happen in one of the two parts, maxProfit = maxProfitInPart1+ maxProfitInPart2. So we apply algorithm of Best Time to Buy and Sell Stock to calculate for a given range what is the maxProfit in this two parts.

e.g:

[1,2,3,4,5,6] - [1,2] and [2,3,4,5,6] or [1,2,3] and [3,4,5,6] or [1,2,3,4] and [4,5,6] or [1,2,3,4,5] and [5,6]

public int maxProfit(int[] prices) {
        if (prices==null||prices.length<2) {
            return 0;
        }

        //key idea: for each price of the day, divide into two range [0, i] and [i+1, n] then find out the maxProfit in this two range.
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];

        int lowestPrice = prices[0];
        for (int i=1; i<prices.length; i++) {
            lowestPrice = Math.min(lowestPrice, prices[i]);
            left[i] = Math.max(left[i-1], prices[i]-lowestPrice);
        }

        int highestPrice = prices[prices.length-1];
        for (int i=prices.length-2; i>=0; i--) {
            highestPrice = Math.max(highestPrice, prices[i]);
            right[i] = Math.max(right[i+1], highestPrice-prices[i]);
        }

        int maxProfit = 0;
        for (int i=0; i<prices.length; i++) {
            maxProfit = Math.max(maxProfit, left[i]+right[i]);
        }

        return maxProfit;        
    }