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

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

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

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param prices int整型一维数组
# @return int整型
#
class Solution:
    def maxProfitIII(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        ans = 0  
        t = prices[n - 1]  
        for i in range(n - 2, -1, -1):
            if prices[i] < t:
                ans += t - prices[i]
            else:
                t = prices[i]
        return ans