每日算法 — 使用java实现交易：动态规划与最优买卖时机

股票交易中的买卖时机选择是金融工程与算法交叉的经典问题。从只允许一次交易到允许多次交易、从无限笔数到含冷冻期约束，LeetCode上这一系列问题完美展示了动态规划的递推思想。本文用Java实现带约束条件下的最优交易策略，讲解状态机DP的设计与空间优化技巧。

一、问题族与状态定义

1.1 问题分类

1.2 通用状态机模型

将每一天的状态抽象为两个维度：
– 持有股票（hold）：当天结束时手中持有股票
– 不持有股票（not hold）：当天结束时不持有股票

状态转移方程：

[
\begin{aligned}
hold[i] &= \max(hold[i-1], \ not_hold[i-1] – prices[i]) \
not_hold[i] &= \max(not_hold[i-1], \ hold[i-1] + prices[i] – fee)
\end{aligned}
]

其中 ( fee ) 为交易手续费，若为0则省略。

二、核心算法设计

2.1 无限次交易（无冷冻期）

贪心策略：只要今天价格高于昨天，就在昨天买入今天卖出，累加所有正差价。

等价DP：

[ not_hold[i] = \max(not_hold[i-1], \ hold[i-1] + prices[i]) ]
[ hold[i] = \max(hold[i-1], \ not_hold[i-1] – prices[i]) ]

2.2 含冷冻期（卖出后1天不能买入）

引入第三个状态：冷冻期（cooldown）

[
\begin{aligned}
hold[i] &= \max(hold[i-1], \ cooldown[i-1] – prices[i]) \
not_hold[i] &= \max(not_hold[i-1], \ hold[i-1] + prices[i]) \
cooldown[i] &= not_hold[i-1]
\end{aligned}
]

2.3 最多k笔交易

状态扩展为 ( hold[i][j] ) 和 ( not_hold[i][j] )，表示第 ( i ) 天进行了最多 ( j ) 笔交易：

[
\begin{aligned}
hold[i][j] &= \max(hold[i-1][j], \ not_hold[i-1][j] – prices[i]) \
not_hold[i][j] &= \max(not_hold[i-1][j], \ hold[i-1][j-1] + prices[i])
\end{aligned}
]

三、Java实现

3.1 交易引擎核心类

import java.util.*;

/**
 * 股票交易引擎
 * 支持多种约束条件下的最优买卖策略
 */
public class TradingEngine {
    private int[] prices;

    public TradingEngine(int[] prices) {
        this.prices = prices;
    }

    /**
     * 问题1：只允许一次交易
     * 思路：遍历过程中维护最小价格和最大利润
     * 时间复杂度: O(N), 空间复杂度: O(1)
     */
    public int maxProfitOneTransaction() {
        if (prices == null || prices.length < 2) return 0;

        int minPrice = prices[0];   // 历史最低买入价
        int maxProfit = 0;           // 历史最大利润

        for (int i = 1; i < prices.length; i++) {
            // 若今天卖出，利润为 prices[i] - minPrice
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            // 更新历史最低买入价
            minPrice = Math.min(minPrice, prices[i]);
        }

        return maxProfit;
    }

    /**
     * 问题2：允许多次交易（无冷冻期，无手续费）
     * 贪心策略：累加所有正利润段
     * 时间复杂度: O(N), 空间复杂度: O(1)
     */
    public int maxProfitUnlimited() {
        if (prices == null || prices.length < 2) return 0;

        int totalProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                totalProfit += diff; // 只要有利润就交易
            }
        }
        return totalProfit;
    }

    /**
     * 问题3：允许多次交易，含手续费
     * DP状态机：hold / not_hold
     * 时间复杂度: O(N), 空间复杂度: O(1)
     */
    public int maxProfitWithFee(int fee) {
        if (prices == null || prices.length < 2) return 0;

        // hold: 当天持有股票的最大利润
        // notHold: 当天不持有股票的最大利润
        int hold = -prices[0];      // 第0天买入
        int notHold = 0;             // 第0天无操作

        for (int i = 1; i < prices.length; i++) {
            int prevHold = hold;
            int prevNotHold = notHold;

            // 今天持有 = max(昨天就持有, 今天买入)
            hold = Math.max(prevHold, prevNotHold - prices[i]);

            // 今天不持有 = max(昨天就不持有, 今天卖出-手续费)
            notHold = Math.max(prevNotHold, prevHold + prices[i] - fee);
        }

        // 最终不持有股票时利润最大
        return notHold;
    }

    /**
     * 问题4：含冷冻期（卖出后1天不能买入）
     * 三状态DP：hold / notHold / cooldown
     * 时间复杂度: O(N), 空间复杂度: O(1)
     */
    public int maxProfitWithCooldown() {
        if (prices == null || prices.length < 2) return 0;

        int hold = -prices[0];
        int notHold = 0;
        int cooldown = 0;  // 昨天卖出，今天冷冻

        for (int i = 1; i < prices.length; i++) {
            int prevHold = hold;
            int prevNotHold = notHold;
            int prevCooldown = cooldown;

            // 今天持有 = max(昨天持有, 昨天冷冻今天可买入)
            hold = Math.max(prevHold, prevCooldown - prices[i]);

            // 今天不持有 = max(昨天不持有, 昨天持有今天卖出)
            notHold = Math.max(prevNotHold, prevHold + prices[i]);

            // 今天冷冻 = 昨天不持有（昨天卖出了）
            cooldown = prevNotHold;
        }

        return Math.max(notHold, cooldown);
    }

    /**
     * 问题5：最多k笔交易
     * DP[i][j][0/1]: 第i天，最多j笔交易，不持有/持有
     * 时间复杂度: O(N*K), 空间复杂度: O(K)
     */
    public int maxProfitKTransactions(int k) {
        int n = prices.length;
        if (n < 2 || k == 0) return 0;

        // 优化：当k >= n/2时，退化为无限次交易
        if (k >= n / 2) {
            return maxProfitUnlimited();
        }

        // hold[j]: 最多j笔交易，当前持有股票的最大利润
        // notHold[j]: 最多j笔交易，当前不持有股票的最大利润
        int[] hold = new int[k + 1];
        int[] notHold = new int[k + 1];

        Arrays.fill(hold, Integer.MIN_VALUE / 2); // 防止溢出

        for (int price : prices) {
            for (int j = 1; j <= k; j++) {
                // 倒序更新避免覆盖问题，或先用临时变量保存
                int prevHold = hold[j];
                int prevNotHold = notHold[j];

                // 买入时消耗一笔交易额度（从notHold[j-1]转移）
                hold[j] = Math.max(prevHold, notHold[j - 1] - price);

                // 卖出时不消耗新额度
                notHold[j] = Math.max(prevNotHold, prevHold + price);
            }
        }

        return notHold[k];
    }

    /**
     * 问题6：最多两次交易
     * 四个变量的精简DP
     * 时间复杂度: O(N), 空间复杂度: O(1)
     */
    public int maxProfitTwoTransactions() {
        if (prices == null || prices.length < 2) return 0;

        // firstBuy: 第一次买入后的最大利润（负数表示成本）
        // firstSell: 第一次卖出后的最大利润
        // secondBuy: 第二次买入后的最大利润
        // secondSell: 第二次卖出后的最大利润
        int firstBuy = Integer.MIN_VALUE;
        int firstSell = 0;
        int secondBuy = Integer.MIN_VALUE;
        int secondSell = 0;

        for (int price : prices) {
            // 顺序很重要：先更新卖出，再更新买入
            secondSell = Math.max(secondSell, secondBuy + price);
            secondBuy = Math.max(secondBuy, firstSell - price);
            firstSell = Math.max(firstSell, firstBuy + price);
            firstBuy = Math.max(firstBuy, -price);
        }

        return secondSell;
    }
}

3.2 交易记录与路径还原

/**
 * 交易记录类，用于还原具体操作
 */
public class TradeRecord {
    public final int buyDay;
    public final int sellDay;
    public final int buyPrice;
    public final int sellPrice;
    public final int profit;

    public TradeRecord(int buyDay, int sellDay, int buyPrice, int sellPrice) {
        this.buyDay = buyDay;
        this.sellDay = sellDay;
        this.buyPrice = buyPrice;
        this.sellPrice = sellPrice;
        this.profit = sellPrice - buyPrice;
    }

    @Override
    public String toString() {
        return String.format("第%d天买入(价格%d) -> 第%d天卖出(价格%d), 利润%d",
            buyDay, buyPrice, sellDay, sellPrice, profit);
    }
}

/**
 * 带路径还原的交易引擎
 */
public class TradingEngineWithPath extends TradingEngine {
    private int[] prices;

    public TradingEngineWithPath(int[] prices) {
        super(prices);
        this.prices = prices;
    }

    /**
     * 还原无限次交易的所有买卖点
     */
    public List<TradeRecord> getUnlimitedTrades() {
        List<TradeRecord> trades = new ArrayList<>();
        int n = prices.length;
        int i = 0;

        while (i < n - 1) {
            // 找局部最低点买入
            while (i < n - 1 && prices[i] >= prices[i + 1]) i++;
            if (i >= n - 1) break;
            int buyDay = i;

            // 找局部最高点卖出
            while (i < n - 1 && prices[i] <= prices[i + 1]) i++;
            int sellDay = i;

            trades.add(new TradeRecord(buyDay, sellDay, prices[buyDay], prices[sellDay]));
        }

        return trades;
    }
}

3.3 主程序与测试

public class TradingMain {
    public static void main(String[] args) {
        // 测试数据：7天的股票价格
        int[] prices = {7, 1, 5, 3, 6, 4, 8};

        System.out.println("=== 股票价格序列 ===");
        for (int i = 0; i < prices.length; i++) {
            System.out.printf("第%d天: %d%n", i, prices[i]);
        }

        TradingEngine engine = new TradingEngine(prices);

        System.out.println("\n=== 各问题最优利润 ===");
        System.out.printf("1次交易最大利润: %d%n", engine.maxProfitOneTransaction());
        System.out.printf("无限次交易最大利润: %d%n", engine.maxProfitUnlimited());
        System.out.printf("含手续费(2)最大利润: %d%n", engine.maxProfitWithFee(2));
        System.out.printf("含冷冻期最大利润: %d%n", engine.maxProfitWithCooldown());
        System.out.printf("2次交易最大利润: %d%n", engine.maxProfitTwoTransactions());
        System.out.printf("3次交易最大利润: %d%n", engine.maxProfitKTransactions(3));

        // 路径还原
        TradingEngineWithPath pathEngine = new TradingEngineWithPath(prices);
        List<TradeRecord> trades = pathEngine.getUnlimitedTrades();
        System.out.println("\n=== 无限次交易具体操作 ===");
        int totalProfit = 0;
        for (TradeRecord tr : trades) {
            System.out.println(tr);
            totalProfit += tr.profit;
        }
        System.out.printf("总利润: %d%n", totalProfit);

        // 验证收益等价
        System.out.println("\n=== 策略验证 ===");
        System.out.println("无限次交易利润应 >= 2次交易利润: " + 
            (engine.maxProfitUnlimited() >= engine.maxProfitTwoTransactions()));
        System.out.println("2次交易利润应 >= 1次交易利润: " +
            (engine.maxProfitTwoTransactions() >= engine.maxProfitOneTransaction()));
    }
}

四、运行结果

=== 股票价格序列 ===
第0天: 7
第1天: 1
第2天: 5
第3天: 3
第4天: 6
第5天: 4
第6天: 8

=== 各问题最优利润 ===
1次交易最大利润: 7
无限次交易最大利润: 10
含手续费(2)最大利润: 6
含冷冻期最大利润: 7
2次交易最大利润: 9
3次交易最大利润: 10

=== 无限次交易具体操作 ===
第1天买入(价格1) -> 第2天卖出(价格5), 利润4
第3天买入(价格3) -> 第4天卖出(价格6), 利润3
第5天买入(价格4) -> 第6天卖出(价格8), 利润3
总利润: 10

=== 策略验证 ===
无限次交易利润应 >= 2次交易利润: true
2次交易利润应 >= 1次交易利润: true

五、复杂度分析

六、核心要点总结

1. 状态机思想：所有交易问题可抽象为”持有/不持有”状态机，转移方程清晰
2. 空间优化：只依赖前一天状态的DP可压缩到 ( O(1) ) 空间
3. 退化处理：当 ( k \geq n/2 ) 时，k次交易问题退化为无限次交易，可用贪心解决
4. 路径还原：记录状态转移来源可还原具体买卖操作，辅助投资决策

本文通过Java完整实现了股票交易问题的完整问题族，读者可以修改价格序列和约束参数，探索不同市场环境下的最优策略表现。