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

Understand the problem:
The problem is an extension to the previous question. The mainly difference is you can complete two transactions at most. So the logic is like: 

• 0 transactions
• 1 transactions:  buy -> sell
• 2 transactions:  buy -> sell -> buy -> sell

Naive Solution:
We can divide the array into two halves, and calculate the maximal profit with only one transaction at each half. So the overall time complexity would be O(n^2). 

DP Solution:
We can define two DP arrays. The first DP array, called left[n] denotes the maximal profit from 0 to i, where as the second DP array, called right[n] denotes the maximal profits from n -1 to i. So the maximal profit is to add them up. 

Code (Java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        
        process(prices, left, right);
        
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        
        return maxProfit;
    }
    
    private void process(int[] prices, int[] left, int[] right) {
        // find out the maximal profit from 0 to i
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            left[i] = Math.max(left[i - 1], prices[i] - min);
            
            min = Math.min(min, prices[i]);
        }
        
        // Find out the maximal profit from n - 1 to i
        int max = prices[prices.length -1];
        for (int i = prices.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], max - prices[i]);
            
            max = Math.max(max, prices[i]);
        }
    }
}

Updates on 10/13/14:
Since the question asks for at most two transactions. For day i, we can get the maximal profit from [0, i], and the maximal profit from [i, end]. Finding the maximal profit from day [0, i] is relative easier to understand. Use a dp_left[i] stands for maximal profit from day 0 to day i. Getting the best profit from profit from day [i, end] is a bit trickier. If we still scan in forward order, for each element i, we need to scan all its following elements, so the complexity would be O(n ^ 2). If we scan from end in backward order, we need to only scan the array once. Then the maximal profit is the maximal sum of the two arrays given a day.