在最多两次交易的限制下买卖股票的最佳时间

Question

本网站提出的问题：https://www.interviewbit.com/problems/best-time-to-buy-and-sell-stocks-iii/

假设你有一个数组，其中第i个元素是给定股票在第i天的价格。

设计一个算法来寻找最大利润。您最多可以完成两笔交易。

注意：你不能同时进行多笔交易（即，你必须在再次购买之前卖出股票）。

我的解决方案：

int Solution::maxProfit(const vector<int> &A) {
    int i = 0, sz = A.size();
    int buy_price, sell_price;

    int profit, max_profit1 = 0, max_profit2 = 0;

    while(i<sz){
        while(i<sz-1 && A[i+1] < A[i]) ++i;
        buy_price = A[i];
        while(i<sz-1 && A[i+1] > A[i]) ++i;
        sell_price = A[i];
        profit = sell_price-buy_price;

        if(profit > max_profit2) {
            swap(max_profit1, max_profit2);
            max_profit2 = profit;
        }
        else if(profit > max_profit1) max_profit1 = profit;

        ++i;
    }

    return max_profit1 + max_profit2;
}

我的想法是跟踪所有利润（我以当地最低价格买进，以当地最高价格卖出）；然后选前两个。我跟踪变量max_profit1和max_profit2中的两个最大利润，其中max_profit1

我尝试了各种情况，并得到了理想的答案，但我面临的OJ提交错误。请帮我指出方法中的缺陷——希望在本案中避免DP。提前谢谢！

Answer 1

对于以下输入，这将失败：[1,2,4,2,5,7,2,4,9,0]

在这种情况下，答案应该是13。（第一天买入，第六天卖出，第七天买入，第九天卖出）。

但根据代码，它返回12。

Answer 2

为什么要避免动态规划？

如果我们向后迭代，我们知道每个可能的买入的最佳卖出量——这是迄今为止看到的最大值。我们还可以记录和更新从我们所在的位置到结束的最佳交易。

如果我们反复向前看，我们知道每一次可能的卖出都是最佳买入——这是迄今为止看到的最小值。我们还可以记录和更新从现在开始的最佳交易。我们可以通过将我们现在的位置与我们已经为百思买记录的交易配对来更新整体解决方案，从索引i1到最后。

Answer 3

本地最小值和最大值可能不是最佳值，因为我们有2个可用交易。

您的代码有时使用错误的本地最小值/最大值

例如给定输入：

1 1 3 1 3 2 4

您的解决方案给出：4

正确的asnwer是：5