121. Best Time to Buy and Sell Stock

題目 / Problem

中文： 給你一個陣列 prices，其中 prices[i] 是某支股票在第 i 天的價格。

你想要透過選擇 某一天 買入這支股票，並在 未來的某一天 賣出，來最大化你的利潤。

回傳你能從這筆交易中獲得的最大利潤。如果無法獲利，回傳 0。

English: You are given an array prices where prices[i] is the price of a stock on day i.

You want to maximize profit by choosing one day to buy and a later day to sell. Return the maximum profit; if no profit is possible, return 0.

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

Worked example / 範例：

Input:  prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6) → profit = 6 - 1 = 5.
        在第 2 天買入（價格 1），第 5 天賣出（價格 6），利潤 = 5。

名詞解釋 / Glossary

• 暴力法 / brute force：嘗試所有可能的組合（這裡是所有 (買, 賣) 的日期配對），從中挑出最好的答案。直觀但通常太慢。
• 單次掃描 / single pass：只把陣列從頭到尾走一遍（O(n)），不需要巢狀迴圈。
• 動態規劃 / dynamic programming (DP)：把一個大問題拆成可以重複使用的子問題；本題的子問題是「到第 i 天為止看到的最低價」。
• 不變量 / invariant：在迴圈每一輪結束時都成立的性質。本題的不變量是：minPrice 永遠是 prices[0..i] 中的最小值，maxProfit 永遠是「任何在第 i 天或之前賣出」的最大利潤。
• INT_MAX：C/C++ 標準函式庫提供的常數，代表 int 型別能存的最大值。我們用它當作 minPrice 的初始值，這樣第一個價格一定會更新它。
• std::min / std::max：C++ 標準函式庫的函式，回傳兩個值中較小 / 較大者。C 語言用三元運算子 a < b ? a : b 達成同樣效果。

思路

最直觀的方法是 暴力法：對每一對 (i, j)（其中 i < j），計算 prices[j] - prices[i]，並追蹤最大值。但是 prices.length 可達 10^5，雙重迴圈是 O(n²) = 10^10 次運算，會超時。

關鍵觀察：當我們在第 j 天「賣出」時，最佳買入日一定是 j 之前價格最低的那一天。所以我們不需要枚舉所有買入日；只要在從左到右掃描的過程中，一邊維護目前看過的最低價 minPrice，一邊用 prices[j] - minPrice 更新答案 maxProfit 就夠了。這樣只需一次掃描，時間 O(n)，空間 O(1)。

不變量是：每處理完第 j 天後，minPrice 等於 prices[0..j] 的最小值，而 maxProfit 等於「在 0..j 中任意買、在 0..j 中任意更晚賣」所能得到的最大利潤。注意更新順序：應先用當前價更新 maxProfit（用「之前」的 minPrice），再更新 minPrice，否則會在同一天買入又賣出（利潤恆為 0），雖然不會出錯，但邏輯上更清楚的做法是先算利潤、再更新最低價。

The brute-force idea is to try every pair (i, j) with i < j and track the largest prices[j] - prices[i]. With n up to 10^5, that's O(n²) which is far too slow. The key insight is that when we decide to sell on day j, the best matching buy day is the cheapest day strictly before j. So instead of enumerating buys, we sweep left-to-right and keep two running values: minPrice (the smallest price seen so far) and maxProfit (the best profit achievable so far). At each new day we first compute prices[j] - minPrice as a candidate sell, update maxProfit, then refresh minPrice. This runs in O(n) time and O(1) space — a single pass with two scalar variables, a textbook example of trading a nested loop for a smartly maintained invariant (a one-state DP).

逐步走查 / Walkthrough

Trace prices = [7, 1, 5, 3, 6, 4]. Start with minPrice = +∞ (we use INT_MAX) and maxProfit = 0.

最終 maxProfit = 5，對應在第 1 天買入（價 1），第 4 天賣出（價 6）。 Final answer is 5, matching buying at price 1 (day 1) and selling at price 6 (day 4).

Solution — C

// Algorithm: one-pass sweep. Maintain the minimum price seen so far (minPrice)
// and the best profit so far (maxProfit). At each day, the best profit if we
// SELL today is prices[i] - minPrice; take the max over all days.
// 演算法：單次掃描，維護目前最低價與目前最大利潤；每天用「今天賣 - 之前最低買」更新答案。

#include <limits.h>   // 引入 INT_MAX 常數 / brings in INT_MAX (largest int value)

int maxProfit(int* prices, int pricesSize) {
    // prices 是指向 int 陣列首元素的指標；pricesSize 是長度。
    // prices is a pointer to the first int of the array; pricesSize is its length.

    int minPrice = INT_MAX;   // 到目前為止看過的最低價，初始設為極大值，第一個價格必定更新它
                              // smallest price seen so far; start huge so the 1st price overwrites it
    int maxProfit = 0;        // 到目前為止能獲得的最大利潤，至少為 0（不交易）
                              // best profit so far; at least 0 (the "do nothing" option)

    for (int i = 0; i < pricesSize; i++) {        // 從第 0 天走到最後一天 / iterate every day
        int today = prices[i];                    // 取出今天的價格（指標索引等同於 *(prices + i)）
                                                  // today's price; arr[i] in C is just *(arr + i)
        int profitIfSellToday = today - minPrice; // 假設今天賣出，能賺多少（之前用最低價買）
                                                  // profit if we sold today after buying at the cheapest past day
        if (profitIfSellToday > maxProfit) {      // 比目前紀錄更高就更新 / keep the best
            maxProfit = profitIfSellToday;        // 更新答案 / update answer
        }
        if (today < minPrice) {                   // 同時更新最低價，供未來幾天使用
                                                  // also refresh the running minimum for future days
            minPrice = today;                     // 注意：先算利潤、再更新最低價，避免「同一天買賣」
                                                  // order matters: compute profit BEFORE lowering minPrice
        }
    }

    return maxProfit;   // 回傳最大利潤；若全程下跌則為 0 / return best profit; 0 if prices only fall
}

Solution — C++

// Algorithm: same single-pass DP. Track minPrice (cheapest day seen so far)
// and maxProfit (best sell profit so far) in O(n) time and O(1) extra space.
// 演算法：與 C 版相同的單次掃描，時間 O(n)，額外空間 O(1)。

#include <vector>      // std::vector：動態陣列容器 / dynamic array container
#include <algorithm>   // std::min / std::max：取兩數較小 / 較大值
#include <climits>     // INT_MAX：int 最大值 / largest int value

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        // vector<int>& 是「對 int 動態陣列的參考」，避免複製整個陣列
        // vector<int>& is a reference to the vector — passed without copying

        int minPrice  = INT_MAX;   // 目前最低買價 / cheapest buy price seen so far
        int maxProfit = 0;         // 目前最大利潤，至少為 0 / best profit; floor at 0

        for (int price : prices) {                      // range-for：逐一取出每個價格
                                                        // range-for loop: iterate values directly
            maxProfit = std::max(maxProfit, price - minPrice);
            // 假設今天賣，利潤 = price - minPrice；與舊答案取較大者
            // if we sold today, profit = price - minPrice; keep the larger of old vs new
            minPrice  = std::min(minPrice, price);
            // 更新最低買價，供之後的天數使用 / refresh cheapest buy for future days
        }

        return maxProfit;   // 一次掃描後回傳答案 / return after one full pass
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只對 prices 做一次線性掃描，每個元素做 O(1) 的比較與更新；n 是 prices.length。We touch each of the n elements exactly once with constant work per element.
• Space: O(1) — 只用了 minPrice 與 maxProfit 兩個整數變數，與輸入大小無關。Only two scalar variables are kept; nothing scales with n.

Pitfalls & Edge Cases

• 回傳 0 而非負數 / return 0, not a negative number：題目要求「無法獲利時回傳 0」。把 maxProfit 初始為 0 而不是 INT_MIN，自然就避免了回傳負利潤的錯誤。Initializing maxProfit = 0 directly enforces the "no profit" rule.
• 必須先買後賣 / must buy before sell：先用 minPrice 算利潤再更新 minPrice，可確保「賣出日」嚴格晚於「買入日」（即使先更新也只會使利潤為 0，不會出錯，但這個順序在邏輯上更乾淨）。Computing profit before lowering minPrice keeps the buy-day strictly earlier than the sell-day in spirit.
• minPrice 初始化 / initializing minPrice：用 INT_MAX 而非 0。若初始為 0，第一天的「假想利潤」會是 prices[0] - 0 = prices[0]，等於把答案誤算成第 0 天的價格。Using INT_MAX makes the first iteration always overwrite it correctly.
• 單元素陣列 / single-element array：prices.length 最小可為 1。迴圈仍會跑一次，但因為 minPrice 在計算利潤時還是 INT_MAX，profitIfSellToday 為負，不會更新 maxProfit，最終回傳 0。正確。Length-1 input correctly returns 0 because no sell can come after the single day.
• 整數溢位 / integer overflow：價格上限 10^4，利潤上限 10^4，遠小於 INT_MAX (≈ 2.1×10^9)，因此 int 完全夠用，不需要 long long. No overflow concerns at this scale.
• 價格全為遞減 / monotonically decreasing prices：如 [7,6,4,3,1]，每天的「假想利潤」皆為負或 0，maxProfit 始終為初始值 0。Correct by construction.