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