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

Analysis

Example:

prices = [4, 4, 6, 1, 1, 4, 2, 5]

f: 从左边开始到i为止取一个区间的最大profit。
f[0]从0到0，一定为0。
f[i]：取当前price和valley的差值，和f[i-1]比较。

f = [0, 0, 2, 2, 2, 3, 3, 4]

g: 从右边开始到i为止取一个区间的最大profit。
g[n-1]从n-1到n-1，一定为0。
g[i]：取当前price和peak的差值，和g[i+1]比较。

g = [4, 4, 4, 4, 4, 3, 3, 0]

f+g = [4, 4, 6, 6, 6, 6, 6, 4]

最大值return 6

Code

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

        int[] f = new int[len]; 
        int[] g = new int[len];

        for (int i=1, valley = prices[0]; i<len; i++){
            f[i] = Math.max(f[i-1], prices[i]-valley);
            valley = Math.min(valley, prices[i]);
        }

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

        int maxProf = 0;

        for (int i=0; i<len; i++){
            maxProf = Math.max(maxProf, f[i]+g[i]);
        }

        return maxProf;
    }
}

Reference