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).
这道是买股票的***时间系列问题中最难最复杂的一道，前面两道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的差值，和前一天的局部最优加上差值中取较大值，而全局最优比较局部最优和前一天的全局最优。代码如下：
解法一：
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]; 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]值，而非已经被覆盖过的值，参见代码如下：
解法二：
class Solution { public: int maxProfit(vector<int> &prices) { if (prices.empty()) return 0; int g[3] = {0}; int l[3] = {0}; for (int i = 0; i < prices.size() - 1; ++i) { int diff = prices[i + 1] - prices[i]; 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]; } };
本文转自博客园Grandyang的博客，原文链接：买股票的***时间之三[LeetCode] Best Time to Buy and Sell Stock III ，如需转载请自行联系原博主。