123. Best Time to Buy and Sell Stock III (Hard)
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).
Solution 1: DP 6ms
version 1:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int hold1 = INT_MIN, hold2 = INT_MIN;
int release1 = 0, release2 = 0;
for (int p:prices) { // Assume we only have 0 money at first
release2 = max(release2, hold2+p); // The maximum if we've just sold 2nd stock so far.
hold2 = max(hold2, release1-p); // The maximum if we've just buy 2nd stock so far.
release1 = max(release1, hold1+p); // The maximum if we've just sold 1nd stock so far.
hold1 = max(hold1, -p); // 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.
}
};
version 2:
First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).
sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i] + buy1, we want to make this max.
buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max
sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.
So sell2 is the most money we can have.
Hope it is helpful and welcome quesions!
class Solution {
public:
int maxProfit(vector<int>& prices) {
int buy1 = INT_MIN, buy2 = INT_MIN;
int sell1 = 0, sell2 = 0;
for (int p: prices) {
buy1 = max(buy1, -p);
sell1 = max(sell1, buy1+p);
buy2 = max(buy2, sell1-p);
sell2 = max(sell2, buy2+p);
}
return sell2;
}
};
Solution 2: DP 6ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
int K = 2, maxProf = 0;
vector<vector<int>> f(K+1, vector<int>(prices.size(),0));
for (int kk = 1; kk <= K; ++kk) {
int tmpMax = f[kk-1][0] - prices[0];
for (int ii = 1; ii < prices.size(); ++ii) {
f[kk][ii] = max(f[kk][ii-1], prices[ii]+tmpMax);
tmpMax = max(tmpMax, f[kk-1][ii]-prices[ii]);
maxProf = max(f[kk][ii], maxProf);
}
}
return maxProf;
}
};
Solution 3: DP
这道是买股票的最佳时间系列问题中最难最复杂的一道，前面两道Best Time to Buy and Sell Stock 买卖股票的最佳时间和Best Time to Buy and Sell Stock II 买股票的最佳时间之二的思路都非常的简洁明了，算法也很简单。而这道是要求最多交易两次，找到最大利润，还是需要用动态规划Dynamic Programming来解，而这里我们需要两个递推公式来分别更新两个变量local和global，参见网友Code Ganker的博客，我们其实可以求至少k次交易的最大利润，找到通解后可以设定 k = 2，即为本题的解答。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：
local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff)
global[i][j]=max(local[i][j],global[i-1][j])，
其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值中取较大值，而全局最优比较局部最优和前一天的全局最优。代码如下：
version 1: 12ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int n = prices.size(), g[n][3] = {0}, l[n][3] = {0};
for (int i = 1; i < prices.size(); ++i) {
int diff = prices[i]-prices[i-1]; // buy on i-1 sell on ith day
for (int j = 1; j <= 2; ++j) {
l[i][j] = max(g[i-1][j-1]+max(diff, 0),l[i-1][j]+diff);
g[i][j] = max(l[i][j], g[i-1][j]);
}
}
return g[n-1][2];
}
};
下面这种解法用一维数组来代替二维数组，可以极大的节省了空间，由于覆盖的顺序关系，我们需要j从2到1，这样可以取到正确的g[j-1]值，而非已经被覆盖过的值，参见代码如下：
我们如果假设prices数组为1, 3, 2, 9, 那么我们来看每次更新时local 和 global 的值：
第一天两次交易： 第一天一次交易：
local: 0 0 0 local: 0 0 0
global: 0 0 0 global: 0 0 0
第二天两次交易： 第二天一次交易：
local: 0 0 2 local: 0 2 2
global: 0 0 2 global: 0 2 2
第三天两次交易： 第三天一次交易：
local: 0 2 2 local: 0 1 2
global: 0 2 2 global: 0 2 2
第四天两次交易： 第四天一次交易：
local: 0 1 9 local: 0 8 9
global: 0 2 9 global: 0 8 9
version 2: 6ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int n = prices.size(), g[3] = {0}, l[3] = {0};
for (int i = 1; i < prices.size(); ++i) {
int diff = prices[i]-prices[i-1]; // buy on i-1 sell on ith day
for (int j = 2; j >= 1; --j) {
l[j] = max(g[j-1]+max(diff, 0),l[j]+diff);
g[j] = max(l[j], g[j]);
}
}
return g[2];
}
};
Solution 4: Two Sweep 12ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<int> left(len), right(len);
int mn = INT_MAX, localMax = 0;
for (int i = 0; i < len; ++i) {
if (prices[i] < mn) mn = prices[i];
else localMax = max(localMax,prices[i]-mn);
left[i] = localMax;
}
int mx = 0; localMax = 0;
for (int i = len-1; i >= 0; --i) {
if (prices[i] > mx) mx = prices[i];
else localMax = max(localMax,mx-prices[i]);
right[i] = localMax;
}
// [0...i-1], [i...n-1]
for (int i = 0; i < len; ++i) {
localMax = max(localMax, left[i]+right[i]);
}
return localMax;
}
};
version 2: 9ms
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) return 0;
int len = prices.size();
vector<int> dp(len+1,0);
int valley = prices[0];
for (int i = 1; i < len; ++i) {
dp[i+1] = max(dp[i], prices[i]-valley);
valley = min(valley, prices[i]);
}
int peak = prices[len-1];
for (int i = len-2; i >= 0; --i) {
dp[i] += max(0, peak-prices[i]);
peak = max(peak,prices[i]);
}
// [0...i-1], [i...n-1]
int res = 0;
for (int i = 0; i <= len; ++i) {
res = max(dp[i], res);
}
return res;
}
};