题解 | #牛群买卖计划#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题目要求在最多进行三次买卖的情况下计算农场主人能获得的最大利润。每次买卖包括一次买入和一次卖出，而且在买入新的牛之前必须已经卖掉手头上的牛。

为了解决这个问题，我们可以使用动态规划来计算最大利润。我们需要定义六个状态变量，分别表示第一次买入、第一次卖出、第二次买入、第二次卖出、第三次买入和第三次卖出的状态。然后，我们遍历数组中的每个价格，并根据六个状态变量来更新利润。

具体解答步骤如下：

初始化六个状态变量 buy1、sell1、buy2、sell2、buy3 和 sell3 分别为正无穷大，表示第一次买入、第一次卖出、第二次买入、第二次卖出、第三次买入和第三次卖出的状态。
遍历数组中的每个价格，对于每个价格 price，我们更新六个状态变量：buy1：取当前价格和上次买入状态的较小值。sell1：取当前价格和上次买入状态的较大值。buy2：取当前价格减去上次卖出状态的较小值。sell2：取当前价格减去上次买入状态和上次卖出状态的较大值。buy3：取当前价格减去第二次卖出状态的较小值。sell3：取当前价格减去第二次买入状态和第二次卖出状态的较大值。
最终，sell3 就是农场主人最多能获得的利润。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MAX;
        int sell1 = 0;
        int buy2 = INT_MAX;
        int sell2 = 0;
        int buy3 = INT_MAX;
        int sell3 = 0;

        for (int price : prices) {
            // 第一次买入的最低价格
            buy1 = min(buy1, price);
            // 第一次卖出后的最大利润
            sell1 = max(sell1, price - buy1);
            // 第二次买入的最低价格，考虑第一次卖出后的利润
            buy2 = min(buy2, price - sell1);
            // 第二次卖出后的最大利润，考虑第二次买入后的利润
            sell2 = max(sell2, price - buy2);
            // 第三次买入的最低价格，考虑第二次卖出后的利润
            buy3 = min(buy3, price - sell2);
            // 第三次卖出后的最大利润，考虑第三次买入后的利润
            sell3 = max(sell3, price - buy3);
        }

        return sell3;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！