Best Time to Buy and Sell Stock III leetcode

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

可以做两次交易, 所以划分两个区间left 长度为0 ~ i, right 长度为 i ~ len-1

left[i] 表示在i点之前买进并卖出能获得的最大利润 

维护一个最小值min, 每次递归的profit最大值为max[A[i] - min, profit]

right[i]表示i点之后买进 最终之前卖出的最大利润

维护一个最大值max 每次递归profit最大值为max[profit, max - A[i]]

所以利润为profit[i] = left[i] + right[i]

最终的最大利润就是Max(profit[i])
时间O(n)空间O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0 || prices == null) {
            return 0;
        }
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < len; i++) {
            min = Math.min(min, prices[i]);
            left[i] = Math.max(left[i-1], prices[i] - min);
        }
        right[len - 1] = 0;
        int max = prices[len - 1];
        for (int j = len - 2; j >= 0; j--) {
            max = Math.max(max,prices[j] );
            right[j] = Math.max(right[j + 1],max -prices[j]);
        }
        int profit = 0;
        for (int k = 0; k < len; k++) {
            profit = Math.max(profit, left[k] + right[k]);
        }
        return profit;
    }
}