动态规划困难1 种解法

#123买卖股票的最佳时机 III

最多完成两笔交易且同一时间只能持有一股，求最大利润。

#数组#动态规划#状态机#股票

解题主线

四个有效交易状态依次是第一次买入、第一次卖出、第二次买入、第二次卖出。

将状态初始化为 -prices[0]、0、-prices[0]、0，表示至多完成两笔交易，允许用零收益的虚拟交易衔接状态。

更新顺序必须保证每个状态只依赖同一天更早的交易阶段或自身旧值；同日零利润买卖不改变最优答案。

解法 1：四状态动态规划

用四个变量记录每个交易阶段结束后的最大现金，逐日按第一次买、第一次卖、第二次买、第二次卖更新。

时间复杂度

O(n)

空间复杂度

O(1)

123. 买卖股票的最佳时机 III · 四状态动态规划

java

final class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int firstBuy = -prices[0];
        int firstSell = 0;
        int secondBuy = -prices[0];
        int secondSell = 0;

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            int previousFirstBuy = firstBuy;
            int previousFirstSell = firstSell;
            int previousSecondBuy = secondBuy;
            int previousSecondSell = secondSell;

            firstBuy = Math.max(previousFirstBuy, -price);
            firstSell = Math.max(previousFirstSell, previousFirstBuy + price);
            secondBuy = Math.max(previousSecondBuy, previousFirstSell - price);
            secondSell = Math.max(previousSecondSell, previousSecondBuy + price);
        }
        return secondSell;
    }
}

用四个变量记录每个交易阶段结束后的最大现金，逐日按第一次买、第一次卖、第二次买、第二次卖更新。

这是旧源码五状态表的等价空间压缩；“未操作”状态恒为 0，无需单独存储。

边界与易错点

旧文件名 Q122_maxStockProfit_III 的题号错误：内容是最多两笔交易，对应真实题号 123，而不是 122。
第二次买入要从第一次卖出后的现金转移，不能再次直接从 0 买入。
返回第二次卖出状态表示最多两笔交易；其初值为 0，因此不交易或只交易一次也被覆盖。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q122_maxStockProfit_III.java