题解 | #牛群买卖计划#

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

1. buy1 表示第一次买入的最低价格，sell1 表示第一次卖出后的最大利润，buy2 表示第二次买入的最低价格（考虑第一次卖出后的利润），sell2 表示第二次卖出后的最大利润（考虑第二次买入后的利润），buy3 表示第三次买入的最低价格（考虑第二次卖出后的利润），sell3 表示第三次卖出后的最大利润（考虑第三次买入后的利润）
2. 在遍历价格数组时，我们根据当前价格以及之前的卖出情况来更新这些变量。具体而言，在每个价格上：
3. 我们首先更新 buy1 和 sell1，分别为当前价格和当前价格减去之前的最低价格。
4. 然后基于上一步的 sell1 来更新 buy2 和 sell2，分别为当前价格减去上一步的 sell1 和当前价格减去之前的最低价格。
5. 接着基于上一步的 sell2 来更新 buy3 和 sell3，分别为当前价格减去上一步的 sell2 和当前价格减去之前的最低价格。
6. 最终返回 sell3 作为最大利润。

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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param prices int整型一维数组
# @return int整型
#
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1 = float("inf")
        sell1 = 0
        buy2 = float("inf")
        sell2 = 0
        buy3 = float("inf")
        sell3 = 0

        for price in 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