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

如果当前节点的解,既依赖于前驱问题的解,又依赖于后驱问题的解,但这两部分又互相独立,则可以分别自左开始DP,计算从最左节点到当前节点的结果;自右开始DP,计算从最右节点到当前节点的结果;再用同一个DP Table来合并解。

假设在i位置买入,j位置卖出,那么对于i,j之间的某个节点,如何计算其利润?可以分成两部分计算:从i到当前节点的利润,这部分只和前驱问题有关;从当前节点到j的利润,这部分只依赖于后驱问题。并且这两部分相互独立,可以把结果叠加在DP Table上。直观上说,相当于在当天卖出又立刻买进,相当于增加了两次虚拟操作。因此,可以以当前节点为分界线,第一次DP自左向右,只计算到当前为止可获得的最大收益(即从之前某天买入,当前卖出的最大收益);第二次DP自右向左,计算从当前开始可获得的最大收益(即从当前买入,之后某天卖出的最大收益)。两部分收益之和即为总收益。

dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }. 0 <= i <= N-1

Complexity

两轮遍历,时间复杂度 O(n),空间复杂度 O(n)

Code

int maxProfit(int[] prices){
    if (prices == null || prices.length < 2) {
        return 0;
    }
 
    //highest profit in 0 ... i
    int[] left = new int[prices.length];
    int[] right = new int[prices.length];
 
    // DP from left to right
    left[0] = 0; 
    int min = prices[0];
    for (int i = 1; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        left[i] = Math.max(left[i - 1], prices[i] - min);
    }
 
    // DP from right to left
    right[prices.length - 1] = 0;
    int max = prices[prices.length - 1];
    for (int i = prices.length - 2; i >= 0; i--) {
        max = Math.max(max, prices[i]);
        right[i] = Math.max(right[i + 1], max - prices[i]);
    }
 
    int profit = 0;
    for (int i = 0; i < prices.length; i++) {
        profit = Math.max(profit, left[i] + right[i]);
    }
 
    return profit;
}