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).
解题思路一：
既然是两次交易的话，分为左右两个区间即可。先按照一次交易的思路算出交易的最大值，存一个数组里，然后从后往前遍历，找到符合条件的和最大的两个，JAVA实现如下：
public int maxProfit(int[] prices) {
if (prices.length == 0)
return 0;
int[] oneProfit = new int[prices.length];
int buy_price = prices[0], profit = 0;
for (int i = 1; i < prices.length; i++) {
buy_price = Math.min(buy_price, prices[i]);
profit = Math.max(profit, prices[i] - buy_price);
oneProfit[i] = profit;
}
int res = oneProfit[prices.length - 1];
int sell_price = prices[prices.length - 1];
profit = 0;
for (int i = prices.length - 1; i >= 1; i--) {
sell_price = Math.max(sell_price, prices[i]);
profit = Math.max(profit, sell_price - prices[i]);
res = Math.max(res, profit + oneProfit[i - 1]);
}
return res;
}
解题思路二：
一种类似提前购买的思路：
参考https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1%E3%80%82
JAVA实现如下：
public int maxProfit(int[] prices) {
int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
int release1 = 0, release2 = 0;
for(int i:prices){ // Assume we only have 0 money at first
release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far.
hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far.
release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far.
hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far.
}
return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
}