LeetCode 122 Best Time to Buy and Sell Stock II：貪心累加所有上漲段

問題描述

給定股票每日價格數組 prices，可進行多次交易（買入後必須賣出才能再買）。求最大利潤。

核心洞察：所有上漲段利潤之和

例如：[4, 7, 8, 2, 8]
傳統思維：找谷買、找峰賣 → (8-4) + (8-2) = 10
等價轉化：(7-4) + (8-7) + (8-2) = 3 + 1 + 6 = 10
結論：只要後一天比前一天漲，就把差價加到總利潤中。無需關心具體買賣日。

貪心證明

任何連續上漲段 a < b < c < d，利潤 d-a = (b-a)+(c-b)+(d-c)。
將長區間拆解為相鄰日間的微小上漲，總和不變。
下跌段不操作（利潤 0）。
故總最大利潤 = Σ max(0, prices[i] - prices[i-1])。

代碼實現

class Solution {
public:
    int maxProfit(vector& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i-1])
                profit += prices[i] - prices[i-1];
        }
        return profit;
    }
};

Python 實現

class Solution:
    def maxProfit(self, prices):
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))

複雜度

• 時間：O(n)，單次遍歷。
• 空間：O(1)。

系列題對比

總結

Stock II 是貪心算法的教科書級應用。關鍵認知：多次交易下，所有上漲段利潤可無損拆解為相鄰日差價之和。代碼極簡，但需理解背後的數學等價性。面試中可先給貪心解，再討論 DP 通解（狀態機）以展示深度。