Best Time to Buy and Sell Stock III | Leetcode

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

---

Solution: Use linear dynamic programming twice on the array. The first time is from left to right. The second time is from right to left. Each time, capture the maximum profit possible until the given point, either from the left end or the right end. At the end, go through the array one last time, and split the array into two parts, getting the maximum profit from the left part plus the right part.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;

        int[] leftProfit = new int[prices.length];
        int[] rightProfit = new int[prices.length];
        
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            int left = (min < prices[i]) ? (prices[i] - min) : 0;
            leftProfit[i] = Math.max(left, leftProfit[i - 1]);
            min = Math.min(min, prices[i]);
        }
        
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            int right = (max > prices[i]) ? (max - prices[i]) : 0;
            rightProfit[i] = Math.max(right, rightProfit[i + 1]);
            max = Math.max(max, prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = -1; i < prices.length; i++) {
            int left = (i < 0) ? 0 : leftProfit[i];
            int right = (i + 1 < prices.length) ? rightProfit[i + 1] : 0;
            maxProfit = Math.max(maxProfit, left + right);
        }
        
        return maxProfit;
    }
}