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

考察的知识点：动态规划；

解答方法分析：

1. 判断价格数组的是否小于等于1，如果是，则返回0。
2. 初始化变量profit和sell，分别表示总利润和卖出价格，初始值设为0。
3. 从数组倒数第二天开始循环遍历到第一天，依次比当前价格和卖出价格。
4. 如果当前价格小于卖出价格，说明可以进行卖出交易，此时将卖出价格减去当前价格并加入利润中。
5. 如果当前价格大于等于卖出价格，说明无法进行卖出交易，此时更新卖出价格为当前价格。
6. 遍历结束后，返回利润值。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param prices int整型vector
     * @return int整型
     */
    int maxProfitIII(vector<int>& prices) {
        if (prices.size() <= 1) {
            return 0;
        }
        int profit = 0;
        int sell = prices[prices.size() - 1];
        for (int i = prices.size() - 2; i >= 0; i--) {
            if (prices[i] < sell) {
                profit += sell - prices[i];
            } else {
                sell = prices[i];
            }
        }
        return profit;
    }
};