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