LeetCode 筆記：Best Time to Buy and Sell Stock II - 無限次交易最大利潤

題目描述

給定每日股價，可完成任意次數交易（賣出後才能再買），求最大利潤。本質上是求所有「上升段」的價差之和。

貪心證明

對於任意上升段 p[i] < p[i+1] < ... < p[j]，利潤 p[j] - p[i] 等價於逐日差價之和 Σ(p[k+1]-p[k])。因此只需遍歷數組，累加所有 prices[i] > prices[i-1] 的正差價。

代碼實現 (C++ / Java / Python)

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;
    }
};

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

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

複雜度

• 時間：O(n)
• 空間：O(1)

系列對比

總結

Stock II 是系列中最簡單的一題，核心洞見：「只要明天比今天漲，今天就買、明天賣」。這種貪心策略在無限次交易下最優。面試中可順勢引出 Stock III/IV 的 DP 思路，展示知識體系廣度。