Best Time to Buy and Sell Stock III
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.
Given an example [4,4,6,1,1,4,2,5]
, return 6
.
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法
这次的不同点在与要做两次交易,所以我们要找一个分界点,分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次:
第一次是从左到右扫[0-i]区间,也就是先确定buyDay,然后根据每个prices[i]来确定sellDay。
第二次是从右到左扫[i-end]区间,也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。
所以这两个循环时间都是O(n)
最后我们要用一个循环来设分界点,然后取
max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
注意这个max不是最终答案,假设只有两天[1,2] 这种情况算下来是0,因为分界点两边都是1天不足以完成交易,而且有可能的情况是第一天买入,最后一天买进,这种情况按两次交易算也无法取到最大值,所以最后结果还要考虑到只做一次交易的情况,因为没有规定必须做两次交易
Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
这一部分的时间复杂度也是O(n)
所以整体的时间复杂度就是O(n)
public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) { return 0; } int length = prices.length; int[] maxProfitEndedAt = new int[length]; int[] maxProfitStartedFrom = new int[length]; //get the max profit from 0 to i with one transaction maxProfitEndedAt[0] = 0; int buyDay = 0; for (int i = 1; i < length; i++) { maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]); if (prices[i] < prices[buyDay]) { buyDay = i; } } //get the max profit form i to length-1 with one transaction maxProfitStartedFrom[length - 1] = 0; int sellDay = length - 1; for (int i = length - 2; i >= 0; i--) { maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]); if (prices[i] > prices[sellDay]) { sellDay = i; } } //to have two transactions //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1]) int maxWithTwoTransaction = 0; for (int i = 0; i < length - 2; i++) { maxWithTwoTransaction = Math.max(maxWithTwoTransaction, maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]); } return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]); }