122. Best Time to Buy and Sell Stock II

題目 / Problem

中文： 給定一個整數陣列 prices，其中 prices[i] 表示某支股票在第 i 天的價格。

每一天你都可以選擇買入和/或賣出股票。任何時刻你最多只能持有 一股。不過你可以在 同一天 內先賣出再買入（只要不違反「最多持有一股」的限制）。

請回傳你能獲得的 最大利潤。

English: You are given an integer array prices where prices[i] is the stock price on day i. Each day you may buy and/or sell. You can hold at most one share at a time, though you may sell-then-buy on the same day. Return the maximum profit achievable.

Constraints / 限制： - 1 <= prices.length <= 3 * 10^4 - 0 <= prices[i] <= 10^4

Example / 範例： - Input: prices = [7,1,5,3,6,4] - Output: 7 - Explanation: 第 2 天買入 (price = 1)，第 3 天賣出 (price = 5)，利潤 = 4。再於第 4 天買入 (price = 3)，第 5 天賣出 (price = 6)，利潤 = 3。總計 4 + 3 = 7。

名詞解釋 / Glossary

• 貪心演算法 / Greedy algorithm：在每一步都做「當下看起來最好」的選擇，期望能得到全域最佳解。本題每一段價格上漲都立刻收割，是經典的貪心成立場景。
• 動態規劃 / Dynamic programming (DP)：把問題拆成可重複利用的小子問題，靠記憶結果避免重複計算。本題可以用 DP 維護「今天持股 / 不持股」兩個狀態。
• 狀態機 / State machine：用有限的「狀態」（例如「手上有股」或「手上沒股」）以及狀態之間的轉移規則來描述問題。買賣股票題系列常用此模型。
• 陣列 / Array：一段連續記憶體中存放同型別元素的資料結構，使用整數索引存取，例如 prices[i]。
• 時間複雜度 O(n) / Time complexity O(n)：執行時間與輸入長度 n 成正比。本題只需要掃過陣列一次。
• 空間複雜度 O(1) / Space complexity O(1)：除了輸入之外，只用了常數個變數，不隨輸入大小成長。

思路

最直覺的做法是「窮舉所有買賣時機」：列出每一段可能的買入日與賣出日，然後比較總利潤。但這樣會有指數級的組合數，當 n = 3 * 10^4 時根本跑不完。

那有沒有比較聰明的觀察呢？關鍵在於「同一天可以先賣後買」這個條件，意味著任何「在第 i 天買、在第 j 天賣」的長期持有，其利潤 prices[j] - prices[i] 都可以拆解成相鄰兩天的差值總和：(prices[i+1] - prices[i]) + (prices[i+2] - prices[i+1]) + ... + (prices[j] - prices[j-1])。換句話說，我們只要把所有「相鄰兩天的正向價差」全都加起來，就等同於我們在每一段上漲區間都進行了一次「低買高賣」。下跌的日子我們選擇不持股，因此忽略負的價差。這個策略稱為 貪心演算法，每一步只做局部最佳選擇 (賺到正的就拿)，最後就會達到全域最佳。掃一次陣列即可，時間 O(n)，空間 O(1)。

The brute-force idea is to enumerate every possible (buy-day, sell-day) combination, but that is exponential and infeasible for n up to 3 * 10^4. The crucial observation is that holding the stock from day i to day j produces a profit prices[j] - prices[i], which telescopes into the sum of adjacent differences (prices[i+1] - prices[i]) + ... + (prices[j] - prices[j-1]). Because we are allowed to sell and re-buy on the same day, any long hold can be simulated by chaining together one-day holds. So the optimal strategy is simply: for every consecutive pair of days, if the price went up, pocket that gain; if it went down, skip it (pretend we are not holding). That is a textbook greedy choice — locally optimal at each step, and provably globally optimal here. One linear scan does the job in O(n) time and O(1) space.

逐步走查 / Walkthrough

Example: prices = [7, 1, 5, 3, 6, 4]

We walk through each day i from 1 to n-1, checking the diff prices[i] - prices[i-1]. If positive, add to profit; otherwise ignore.

Final answer: profit = 7. ✅

注意第 2 天加上的 +4 對應「day 2 買入、day 3 賣出」；第 4 天加上的 +3 對應「day 4 買入、day 5 賣出」。完全對得上題目給的解釋。

Solution — C

/*
 * 演算法 / Algorithm:
 * 貪心法：把所有相鄰兩天的「正向價差」加總。
 * Greedy: sum up every positive day-to-day price difference.
 * 等價於在每一段上漲區間都執行一次低買高賣。
 * Equivalent to buying at each local low and selling at each local high.
 */

int maxProfit(int* prices, int pricesSize) {
    // profit 累計總利潤，初始化為 0 / running total of profit, starts at 0
    int profit = 0;

    // 從第 1 天開始（索引從 1），每次和前一天比較
    // Loop from day 1 onwards, comparing each day with the previous one
    for (int i = 1; i < pricesSize; i++) {
        // 計算今天比昨天貴多少 / compute how much today is higher than yesterday
        int diff = prices[i] - prices[i - 1];

        // 只有上漲 (diff > 0) 才把這段差價計入利潤；下跌就略過
        // Only count the diff when it is positive; ignore drops
        if (diff > 0) {
            profit += diff;  // 累加上漲幅度 / add the gain to total profit
        }
    }

    // 回傳累計的最大利潤 / return the accumulated maximum profit
    return profit;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 貪心法：對每一對相鄰日期，把正向價差加進總利潤。
 * Greedy: for every adjacent pair of days, add the positive diff to total profit.
 * 一次線性掃描即可，O(n) 時間 / O(1) 空間。
 * One linear pass — O(n) time, O(1) extra space.
 */

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        // profit 累計總利潤 / running total of profit
        // 使用 int 即可：n ≤ 3e4 且 price ≤ 1e4，最大利潤遠小於 INT_MAX
        // int is safe here: with n ≤ 3e4 and price ≤ 1e4, profit fits in int
        int profit = 0;

        // range-for 從索引 1 不太方便，改用傳統 for 迴圈以便存取 i-1
        // Using an indexed for-loop because we need both prices[i] and prices[i-1]
        // size() 回傳 size_t (無號)，這裡 prices 不為空所以安全
        // size() returns size_t (unsigned); prices is guaranteed non-empty by constraints
        for (size_t i = 1; i < prices.size(); ++i) {
            // 計算相鄰兩天的價差 / compute the difference between today and yesterday
            int diff = prices[i] - prices[i - 1];

            // std::max(a, b) 取兩者中較大者；diff 為負時取 0，相當於忽略下跌
            // std::max picks the larger of two values; clipping negatives to 0
            // skips losing days without an explicit if-statement
            profit += std::max(diff, 0);
        }

        // 回傳最大利潤 / return the maximum profit
        return profit;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對 prices 只走訪一次，每個元素做常數次比較與加法。n 是 prices 的長度。 / We scan prices exactly once, doing constant work per element. n is the array length.
• Space: O(1) — 只使用了 profit 與 diff 等少量變數，與輸入大小無關。 / We use only a few scalar variables (profit, diff), independent of n.

Pitfalls & Edge Cases

• 誤以為要找「最大單次交易」/ Confusing this with Problem 121：121 題只允許一次買賣，這裡可以多次。如果套用 121 的「最低買入價」演算法會少算很多利潤。這裡每段上漲都要收割。 / Don't apply the single-transaction algorithm from problem 121 — that would miss profit from later up-runs.
• 長度為 1 的陣列 / Single-element array：pricesSize == 1 時迴圈直接不執行，profit 保持為 0，正確。 / The loop body never runs when there is only one day; we correctly return 0.
• 完全下跌 / Strictly decreasing prices：例如 [7,6,4,3,1]，每個 diff 都 ≤ 0，全部跳過，回傳 0。永遠不會出現負利潤，因為我們可以選擇「不交易」。 / All diffs are non-positive, none are added, and we return 0 — we never go negative because doing nothing is always an option.
• 同一天先賣後買 / Sell-then-buy on the same day：題目允許，因此把長期持有拆解成「每天一段」是合法的。理解這點是貪心解法成立的關鍵。 / This rule is what licenses the telescoping decomposition that makes the greedy approach valid.
• 整數溢位 / Integer overflow：n ≤ 3 * 10^4 且 price ≤ 10^4，理論最大利潤約 1.5 * 10^8，int (約 2.1 * 10^9) 綽綽有餘。 / Profit is bounded well within int range, so no overflow concerns.
• off-by-one 錯誤 / Off-by-one in the loop：迴圈必須從 i = 1 開始，否則 prices[i-1] 會越界讀到 prices[-1]。 / Starting at i = 1 is essential; i = 0 would read out of bounds at prices[-1].