121. Best Time to Buy and Sell Stock

用当前价格减去之前的最低价格来更新全局最大差价即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mn = INT_MAX, res = 0;
        for (int p : prices) {
            res = max(res, p - mn);
            mn = min(mn, p);
        }
        return res;
    }
};

直接切入法
买卖一股，一定是第i天买，第j天卖（j > i），获利是prices[j] - prices[i]
枚举j，即第几天卖，只需要维护当前最低的买入价格prices[i] (i < j)即可

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int curr_min = INT_MAX;
        int res = 0;
        int n = prices.size();
        for (int i = 0; i < n; ++i) {
            curr_min = min(curr_min, prices[i]);
            res = max(res, prices[i] - curr_min);
        }
        return res;
    }
};

maximum subarray法
dp O(n) time O(1) space

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int profit = 0;
        int res = 0;
        for (int i = 1; i < n; ++i) {
            profit = max(profit, 0) + prices[i] - prices[i - 1];
            res = max(res, profit);
        }
        return res;
    }
};

dp O(n) time O(n) space
maximum subarray的变体
(b - a) + (c - b) + (d - c) + (e - d) = e - a

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        vector<int> diffs(n - 1);
        for (int i = 1; i < n; ++i) {
            diffs[i - 1] = prices[i] - prices[i - 1];
        }
        vector<int> dp(n);
        int res = 0;
        for (int i = 1; i < n; ++i) {
            if (dp[i - 1] < 0) {
                dp[i] = diffs[i - 1];
            } else {
                dp[i] = dp[i - 1] + diffs[i - 1];
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};