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 == 0){
return 0;
}
int f[] = new int[len];
int b[] = new int[len];
f[0] = b[len-1] = 0;
int minf = prices[0];
int maxb = prices[len-1];
int ret = 0;
for(int i=1; i<len; i++){
int j = len-1-i;
f[i] = Math.max(f[i-1], prices[i]-minf);
b[j] = Math.max(b[j+1], maxb - prices[j]);
minf = Math.min(minf, prices[i]);
maxb = Math.max(maxb, prices[j]);
ret = Math.max(f[i]+b[i], ret);
}
for(int i = 0; i<len; i++){
ret = Math.max(f[i]+b[i], ret);
}
return ret;
}
}
