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).
之前题的扩展，要求是只能买卖两次，然后求出最大利润。
利用动态规划，从前向后和从后向前各求一次，然后求出结果。
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if( len < 2 )
return 0;
int[] preProfit = new int[len];
int[] maxProfit = new int[len];
int cur = prices[0];
preProfit[0] = 0;
for( int i = 1;i<len;i++){
cur = Math.min(cur,prices[i]);
preProfit[i] = Math.max(preProfit[i-1],prices[i] - cur);
}
cur = prices[len-1];
maxProfit[len-1] = 0;
for( int i = len-2;i>=0;i--){
cur = Math.max(cur,prices[i]);
maxProfit[i] = Math.max(maxProfit[i+1],cur - prices[i]);
}
int result = 0;
for( int i = 0;i<len;i++){
result = Math.max(preProfit[i]+maxProfit[i],result);
}
return result;
}
}