股票买卖问题全集

状态机思路

所有股票题均可用状态机統一，状态：(天数, 持股状态, 已完成交易次数)

// 通用框架：最多 k 次交易
// 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]) // 保持或买入（买入时 k 减少1）

问题 I：只能交易一次（LeetCode 121）

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

问题 II：无限次交易（LeetCode 122）

public int maxProfit(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;
}

问题 III：最多 2 次交易（LeetCode 123）

public int maxProfit(int[] prices) {
    int buy1 = Integer.MIN_VALUE, sell1 = 0, buy2 = Integer.MIN_VALUE, sell2 = 0;
    for (int price : prices) {
        buy1  = Math.max(buy1,  -price);
        sell1 = Math.max(sell1, buy1 + price);
        buy2  = Math.max(buy2,  sell1 - price);
        sell2 = Math.max(sell2, buy2 + price);
    }
    return sell2;
}

问题 IV：最多 k 次交易（LeetCode 188）

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {  // 等价于无限次
        int profit = 0;
        for (int i = 1; i < n; i++) profit += Math.max(0, prices[i] - prices[i-1]);
        return profit;
    }
    int[] buy = new int[k+1], sell = new int[k+1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int price : prices) {
        for (int j = 1; j <= k; j++) {
            buy[j]  = Math.max(buy[j],  sell[j-1] - price);
            sell[j] = Math.max(sell[j], buy[j] + price);
        }
    }
    return sell[k];
}

问题 V：含冷冻期（LeetCode 309）

卖出后下一天不能买入：

public int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int price : prices) {
        int prevSold = sold;
        sold = hold + price;                // 今天卖出
        hold = Math.max(hold, rest - price); // 今天买入必须从 rest 状态
        rest = Math.max(rest, prevSold);    // 今天不操作
    }
    return Math.max(sold, rest);
}

问题 VI：含手续费（LeetCode 714）

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

总结