LeetCode 买卖股票的最佳时机 I：差分数组 + 最大子段和

题目大意

给定数组 prices，prices[i] 表示第 i 天股价。只能完成至多一笔交易（买入后卖出），求最大利润。若无利润返回 0。

核心洞察：差分转最大子段和

设 diff[i] = prices[i+1] - prices[i] 为每日涨跌幅。买卖利润等于连续若干天涨跌幅之和。问题转化为：求差分数组的最大子段和，且下界为 0。

算法实现

#include <iostream>
#include <vector>
using namespace std;

// 最大子段和（Kadane 算法变体，非负下界）
int findMax(int *list, int n) {
    int maxSum = 0, sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += list[i];
        if (sum > maxSum) maxSum = sum;
        else if (sum <= 0) sum = 0; // 关键：负和重置
    }
    return maxSum;
}

int maxProfit(vector<int> &prices) {
    if (prices.empty()) return 0;
    int n = prices.size();
    int *diff = new int[n - 1];
    for (int i = 0; i < n - 1; ++i)
        diff[i] = prices[i + 1] - prices[i];
    int ans = findMax(diff, n - 1);
    delete[] diff;
    return ans;
}

int main() {
    // 测试用例
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    cout << maxProfit(prices) << endl; // 输出 5 (第2天买入1，第5天卖出6)
    return 0;
}

复杂度分析

• 时间 O(n)：单次遍历构造差分 + 单次遍历 Kadane
• 空间 O(n)：差分数组，可优化为 O(1) 原地计算

空间优化版（O(1) 空间）

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

维护历史最低价，单次遍历即可，更简洁高效。

扩展：多次交易 / 冷冻期 / 手续费

• II（多次交易）：贪心累加所有正差分
• III（两次交易）：前缀/后缀最大利润分治
• IV（k 次交易）：DP dp[k][i] 状态压缩
• 含冷冻期/手续费：状态机 DP（持有/未持有/冷冻）

总结

本题是股票系列入门，核心在于「差分视角」与「最大子段和」的等价转化。掌握 Kadane 算法及其非负变体，可解决大量区间最优子结构问题。