NYOJ 739 股票最大利潤：Kadane 算法 O(n) 單掃描

NYOJ 739 - 股票買賣一次最大利潤：最大子段和變種

已知 n 天股價，最多買賣一次（先買後賣），求最大利潤。n < 100000。

核心邏輯：前綴最小值 + 當前利潤

遍歷價格，維護：

• min_price：歷史最低買入價
• max_profit：當前價格 - min_price 的最大值

等價於求差分數組的最大子段和（Kadane 算法）。

代碼實現

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int x, y; scanf("%d", &x);
        int max_profit = 0, min_price = x;
        for (int i=1; i

原文代碼解析
原文用差分 s = y - x，維護 sum（當前子段和），sum < 0 ? sum = s : sum += s 即 Kadane 核心。max = max(max, sum) 記錄最大值。邏輯完全等價。

複雜度
時間 O(n)，空間 O(1)。單次掃描，極其高效。

擴展：多次買賣
若允許多次買賣（不重疊），答案為所有上升段利潤之和：Σ max(0, price[i+1]-price[i])。