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