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

Solution

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

        int size = prices.length;
                if (size == 1) return 0;

        int[] left = new int[size];
        int min = prices[0];

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

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

        int result = Integer.MIN_VALUE;
        for (int i = 0; i <= size - 1; i++) {
            result = Math.max(result, left[i] + right[i]);
        }

        return result;
    }
}