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.

Have you met this question in a real interview? 

Yes

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

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

class Solution {

    /**

     * @param prices: Given an integer array

     * @return: Maximum profit

     */

    public int maxProfit(int[] prices) {

        // write your code here

        int n = prices.length;

        int[] left = new int[n];

        int[] right = new int[n];

        int minIndex = 0;

        int maxProfit = 0;

        for(int i = 1; i < n; i++){

           maxProfit = Math.max(maxProfit, prices[i] - prices[minIndex]);

           left[i] = maxProfit;

           if(prices[i] < prices[minIndex]){

               minIndex = i;

           }

        }

        int maxIndex = n - 1; 

        maxProfit = 0;

        for(int i = n-2; i >= 0; i--){

           maxProfit = Math.max(maxProfit, prices[maxIndex] - prices[i]);

           right[i] = maxProfit;

           if(prices[i] > prices[maxIndex]){

               maxIndex = i;

           }

        }

        maxProfit = 0;

        for(int i = 0; i < n; i++){

            maxProfit = Math.max(left[i]+right[i], maxProfit);

        }

        return maxProfit;

    }

};