题目
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).
答案
这个答案很巧妙，竟然用到了2个dp数组，然后答案要从2个dp数组的信息中提取出来，把分治和dp巧妙结合起来，让我学到很多!
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0) return 0;
int[] left = new int[prices.length];
int[] right = new int[prices.length];
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);
}
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]);
}
max = 0;
for(int i = 0; i < prices.length; i++) {
max = Math.max(max, left[i] + right[i]);
}
return max;
}
}
