买卖股票的最佳时机 II

🟡 Medium · 🏷️ 数组、贪心 · LeetCode#122

📖 题目

跟买卖股票的最佳时机一样给出每天的股价，但这次可以多次买卖（卖出当天就能再买入），求最大利润。

输入	输出	说明
[7,1,5,3,6,4]	7	第2天买第3天卖赚4，第4天买第5天卖赚3
[1,2,3,4,5]	4	连续上涨，逐天赚等于一次性持有到底

💡 思路

不限交易次数，反而让问题变简单了——贪心的局部最优就是全局最优：只要相邻两天在涨，就把这段涨幅收进口袋，跌的时候直接跳过不参与。

逐天赚和一次性持有的结果是一样的：(2-1)+(3-2)+(4-3)+(5-4) 化简正好等于 5-1。所以不用纠结"到底该在哪天买卖"，遍历一遍，把每一段正的涨幅加起来就是答案。

💻 代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            profit += max(prices[i] - prices[i - 1], 0)
        return profit

时间复杂度 O(n)，空间复杂度 O(1)。同一个股票系列，只能交易一次反而要维护历史最低价，不限次数反而是最简单的贪心——限制变少不代表题目变难。