买卖股票系列（6 道全覆盖）

核心思想：股票 DP 状态机

所有股票问题都可用状态机 DP 统一解决：

• 状态：天数 × 交易次数 × 是否持有
• dp[i][k][0] = 第 i 天，最多完成 k 笔交易，不持有股票的最大利润
• dp[i][k][1] = 第 i 天，最多完成 k 笔交易，持有股票的最大利润

状态转移：

dp[i][k][0] = max(dp[i-1][k][0],          // 昨天也没持有（休息）
                  dp[i-1][k][1] + prices[i]) // 昨天持有，今天卖出
dp[i][k][1] = max(dp[i-1][k][1],           // 昨天也持有（休息）
                  dp[i-1][k-1][0] - prices[i]) // 昨天没持有，今天买入

122. 买卖股票的最佳时机 I（k = 1）

int maxProfit1(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        maxProfit = Math.max(maxProfit, p - minPrice);
    }
    return maxProfit;
}

123. 买卖股票的最佳时机 II（k = 无限）

可以任意多次买卖（不同时持有多只）：

int maxProfit2(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1])
            profit += prices[i] - prices[i - 1];
    }
    return profit;
}

贪心：只要今天比昨天贵就"加上差价"。

124. 买卖股票的最佳时机 III（k = 2）

int maxProfit3(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0;
    int buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int p : prices) {
        buy1  = Math.max(buy1,  -p);          // 第一次买入
        sell1 = Math.max(sell1, buy1 + p);    // 第一次卖出
        buy2  = Math.max(buy2,  sell1 - p);   // 第二次买入
        sell2 = Math.max(sell2, buy2 + p);    // 第二次卖出
    }
    return sell2;
}

125. 买卖股票的最佳时机 IV（k = K）

int maxProfitK(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) return maxProfit2(prices); // 退化为无限次
    int[] buy = new int[k], sell = new int[k];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int p : prices) {
        for (int i = 0; i < k; i++) {
            buy[i]  = Math.max(buy[i],  (i == 0 ? 0 : sell[i-1]) - p);
            sell[i] = Math.max(sell[i], buy[i] + p);
        }
    }
    return sell[k - 1];
}

126. 买卖股票含冷冻期

卖出后下一天不能买入：

int maxProfitCooldown(int[] prices) {
    int held = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = held + p;
        held = Math.max(held, rest - p);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

127. 买卖股票含手续费

每次卖出需支付 fee：

int maxProfitFee(int[] prices, int fee) {
    int held = -prices[0], cash = 0;
    for (int i = 1; i < prices.length; i++) {
        held = Math.max(held, cash - prices[i]);
        cash = Math.max(cash, held + prices[i] - fee);
    }
    return cash;
}