C++实现LeetCode(123.买股票的最佳时间之三)

下面我将从几个方面来详细讲解“C++实现LeetCode(123.买股票的最佳时间之三)”的完整攻略。

一、题目描述

本题的题目描述如下：

给定一个数组 prices ，其中 prices[i] 代表某股票在第 i 天的价格。
你最多可以完成两笔交易。计算你所能获取的最大利润。注意：你不能同时参与多笔交易（即，你必须在再次购买之前卖出之前的股票）。

但是，在完成一笔交易后，你可以立刻开始另一笔交易。

二、解题思路

本题可以使用动态规划的方法来解决。我们可以使用四个变量来分别表示在不同的情况下所能获得的最大利润：

• buy1：表示第一次购买股票后所能获得的最大利润；
• buy2：表示第二次购买股票后所能获得的最大利润；
• sell1：表示第一次卖出股票后所能获得的最大利润；
• sell2：表示第二次卖出股票后所能获得的最大利润。

在每一天结束后，我们都需要更新这四个变量的值。具体来说，对于任意一天，可能出现的情况有以下三种：

• 对于 buy1，既可以继续保持不变（因为该天不需要进行任何交易），也可以在该天购买股票（此时需要扣除该天的股票价格）；
• 对于 sell1，既可以继续保持不变（因为该天不需要进行任何交易），也可以在该天卖出第一次购买的股票（获得该天股票价格的收益）；
• 对于 buy2 和 sell2 也是类似的。

因此，在每一天结束后，我们都需要更新这四个变量的值。具体的更新方式如下所示：

• buy1：维持不变，或者买入股票（扣除当前股票价格）；
• sell1：维持不变，或者卖出第一次买入的股票（增加当前的股票价格）；
• buy2：维持不变，或者在卖出第一次买入的股票的前提下买入股票（扣除当前股票价格减去第一次买入的股票所获得的收益）；
• sell2：维持不变，或者卖出第二次买入的股票（增加当前的股票价格减去第二次买入的股票所获得的收益）。

最终的答案即为 sell2。

三、代码实现

下面是用 C++ 实现的代码，同时给出了两个需要特别说明的测试用例，方便理解算法的具体解释。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for(int i=1;i<prices.size();i++){
            int preBuy1 = buy1;
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, preBuy1 + prices[i]); // 可以理解成当天卖出，收益为 preBuy1 + prices[i]
            int preBuy2 = buy2;
            buy2 = max(buy2, sell1 - prices[i]); // 第二次考虑其实是可以理解成在第一次卖出后再次买入，所以是 sell1 而不是 preBuy1
            sell2 = max(sell2, preBuy2 + prices[i]); 
        }
        return sell2;
    }
};

四、代码解释

在实现代码时，需要注意以下几点：

• 第一个交易得到的收益是负数，所以需要使用负数的初始值，这里设置为 -prices[0]；
• 需要注意细节问题，比如第二次购买股票的时候，需要用第一次卖出股票后的收益来抵消购买所需要花费的钱。

五、测试用例

下面给出两个使用本算法的测试用例：

示例 1：

vector<int> prices{3,3,5,0,0,3,1,4};
Solution sol;
int res = sol.maxProfit(prices);
cout << res << endl;
// 此时的 res 的结果为 6

示例 2：

vector<int> prices{1,2,3,4,5};
Solution sol;
int res = sol.maxProfit(prices);
cout << res << endl;
// 此时的 res 的结果为 4

以上就是本题的详细解答，希望能对您有所帮助。