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) {
if (prices.length < 2)
return 0;
if (prices.length ==2 )
return prices[0] < prices[1] ? prices[1] - prices[0] : 0;
int[] maxProf1 = new int[prices.length];
int maxPrice = prices[prices.length-1];
maxProf1[maxProf1.length-1] = 0;
for (int i = maxProf1.length-2; i >=0; i--) {
int profit1;
if (prices[i] > maxPrice) {
profit1 = 0;
maxPrice = prices[i];
}
else {
profit1 = maxPrice - prices[i];
}
maxProf1[i] = profit1 > maxProf1[i+1] ? profit1 : maxProf1[i+1];
}
int minPrice = prices[0];
int maxProf2 = 0;
int maxProf = 0;
for (int j = 0; j < prices.length-2; j++) {
int profit2;
if (prices[j] > minPrice) {
profit2 = prices[j] - minPrice;
}
else {
profit2 = 0;
minPrice = prices[j];
}
maxProf2 = maxProf2 > profit2 ? maxProf2 : profit2;
int profit = maxProf2 + maxProf1[j];
maxProf = maxProf > profit ? maxProf : profit;
}
return maxProf;
}
}
No comments:
Post a Comment