LeetCode 筆記：Best Time to Buy and Sell Stock - 單次交易最大利潤

題目描述

給定每日股價數組，只允許買賣一次（或零次），求最大利潤。即找 i < j 使 prices[j] - prices[i] 最大化。

單遍歷維護最小值（標準解）

遍歷價格，維護至今最小買入價 minPrice，並在每一天計算「若今天賣出」的利潤 prices[i] - minPrice，更新全局最大利潤。

class Solution {
public:
    int maxProfit(vector& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = min(minPrice, price);
            maxProfit = max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
};

逆向遍歷維護最大值（等價思路）

從右向左掃描，維護至今最大賣出價 maxPrice，計算「若今天買入」的利潤 maxPrice - prices[i]。

class Solution {
public:
    int maxProfit(vector& prices) {
        if (prices.empty()) return 0;
        int maxPrice = prices.back();
        int profit = 0;
        for (int i = prices.size() - 1; i >= 0; --i) {
            maxPrice = max(maxPrice, prices[i]);
            profit = max(profit, maxPrice - prices[i]);
        }
        return profit;
    }
};

差分數組 + 最大子段和（理論視角）

構造差分 diff[i] = prices[i] - prices[i-1]，則單次交易利潤等價於差分數組的最大子段和（Kadane 算法）。這揭示了 Stock I 與「最大子數組和」的等價性。