Problem

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.

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


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

思路

• 最多进行两次交易, 并且不能重叠, 所以将该数组划分成两个部分
• [0, i] 和 [i, len - 1]
• left[i] 代表 0 ~ i 这个区间的最大利益
• right[i] 代表 i ~ len-1 这个区间的最大利益
• max_profix = max{ left[i] + right[i] }
• 图中的min代表入货的最小值, max代表出货的最大值

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];

        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);
        }

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

        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans = Math.max(ans, left[i] + right[i]);
        }
        return ans;
    }