123. 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.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
股票买卖题三。这次限制最多交易两次，问最大能获利多少。这确实是个hard题，研一卜神算法作业中遇到过。 先来回顾一下股票买卖第一题LeetCode Best Time to Buy and Sell Stock，当时的做法是从左往右找到除了当前值的最小值min_so_far，然后用当前值减去min_so_far，表示如果在当前卖出（即用min_so_far买入）能获得的最大收益profit1。这一题允许最多两次交易，那么如果求到在当前买入能获得的最大收益profit2，则profit1+profit2表示在当前卖出后买入能获得的最大收益。计算所有的profit1+profit2的最大值，就是两次交易能获得的最大收益。 计算profit2的方法和计算profit1类似，此时我们从右往左找到除了当前值的最大值max_so_far，则用max_so_far减去当前值，就表示在当前买入（max_so_far卖出）能获得的最大收益profit2。
整理一下思路：我们尝试把每个点作为两次交易的分界点，那么这个点在上一个交易中卖出了，同时在下一个交易中买入了，我们要分别求到在这个点卖出和买入能获得的最大收益，然后把两个值加起来就是在这个点两次交易的最大收益。求所有点的最大收益的最大值就是最终结果。 举个例子，如下表，表中的min_so_far和profit1是从左往右计算的，max_so_far和profit2是从右往左计算的，profit1/2计算的都是当前profit和历史profit的最大值，和代码中的含义一致。
| prices | 3 | 2 | 6 | 5 | 0 | 3 |
| min_so_far | INT_MAX | 3 | 2 | 2 | 2 | 0 |
| max_so_far | 6 | 6 | 5 | 3 | 3 | INT_MIN |
| profit1 | 0 | 0 | 4 | 4 | 4 | 4 |
| profit2 | 4 | 4 | 3 | 3 | 3 | 0 |
| total | 4 | 4 | 7 | 7 | 7 | 4 |
完整代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices)
{
int n = prices.size();
if (n < 2)
return 0;
vector<int> minprice(n), maxprice(n);
for (int i = 0; i < n; ++i) {
minprice[i] = i == 0 ? INT_MAX : min(minprice[i – 1], prices[i – 1]);
maxprice[n – i – 1] = i == 0 ? INT_MIN : max(maxprice[n – i], prices[n – i]);
}
vector<int> profit1(n), profit2(n);
for (int i = 0; i < n; ++i) {
profit1[i] = i == 0 ? 0 : max(profit1[i – 1], prices[i] – minprice[i]);
profit2[n – i – 1] = i == 0 ? 0 : max(profit2[n – i], maxprice[n – i – 1] – prices[n – i – 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, profit1[i] + profit2[i]);
}
return ans;
}
};本代码提交AC，用时9MS。
二刷。类似的代码，或许更好理解：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0 || n == 1)return 0;
vector<int> cur_min(n, INT_MAX), cur_max(n, INT_MIN);
cur_min[0] = prices[0];
cur_max[n - 1] = prices[n - 1];
for (int i = 1; i < n; ++i) {
cur_min[i] = min(cur_min[i - 1], prices[i]);
cur_max[n - i - 1] = max(cur_max[n - i], prices[n - i - 1]);
}
vector<int> dp_sell(n, 0), dp_buy(n, 0);
for (int i = 1; i < n; ++i) {
dp_sell[i] = max(dp_sell[i - 1], prices[i] - cur_min[i]);
dp_buy[n - i - 1] = max(dp_buy[n - i], cur_max[n - i - 1] - prices[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, dp_sell[i] + dp_buy[i]);
}
return ans;
}
};本代码提交AC，用时16MS。