题解 | #牛群买卖计划III#

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

题目考察的知识点

贪心算法

题目解答方法的文字分析

这道题目要求在不限制交易次数的情况下计算农场主人能获得的最大利润。农场主人可以选择在某一天买入一头牛，然后在某一天卖出之前买的全部牛。也就是说，农场主人可以在同一天进行多次卖出。

为了解决这个问题，我们可以使用贪心算法。贪心算法是一种每一步都选择当前状态下的最优解的策略。在这道题目中，我们可以从最后一天开始，逆序遍历数组，并不断更新最大售价，同时累加每次买卖的利润。

具体解答步骤如下：

1. 初始化 ans 变量为0，表示初始利润为0。
2. 初始化变量 t 为最后一天的价格 prices[n-1]。
3. 从倒数第二天开始往前遍历 prices 数组，对于每个价格 prices[i]，进行如下操作：如果当前价格 prices[i] 比 t 小，说明可以在当天买入并在最后一天卖出，利润为 t - prices[i]，将利润累加到 ans 中。否则，更新 t 为当前价格 prices[i]，表示重新选择买入的时机。
4. 最终的结果为 ans，表示农场主人能获得的最大利润。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>

using namespace std;

class Solution {
public:
    /**
     * 计算农场主人能在不限制交易次数的情况下获得的最大利润
     * 
     * @param prices int整型vector，表示每天牛的市场价值
     * @return int整型，表示最大利润
     */
    int maxProfitIII(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) {
            return 0;
        }

        int ans = 0;  // 初始化最大利润为0
        int t = prices[n - 1];  // 初始化变量t为最后一天的价格
        for (int i = n - 2; i >= 0; --i) {
            // 从倒数第二天开始往前遍历prices数组
            // 对于每一天的价格prices[i]，进行如下操作：
            if (prices[i] < t) {
                // 如果当前价格prices[i]比t小，说明可以在当天买入并在最后一天卖出
                // 利润为t - prices[i]，将利润累加到ans中
                ans += t - prices[i];
            } else {
                // 否则，更新t为当前价格prices[i]，表示重新选择买入的时机
                t = prices[i];
            }
        }

        return ans;  // 返回最终的结果，表示农场主人能获得的最大利润
    }
};

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