动态规划困难1 种解法
#123买卖股票的最佳时机 III
最多完成两笔交易且同一时间只能持有一股，求最大利润。
#数组#动态规划#状态机#股票
原题
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1] 输出：0
提示：
1 <= prices.length <= 1050 <= prices[i] <= 105
解题主线
- 四个有效交易状态依次是第一次买入、第一次卖出、第二次买入、第二次卖出。
- 将状态初始化为 -prices[0]、0、-prices[0]、0，表示至多完成两笔交易，允许用零收益的虚拟交易衔接状态。
- 更新顺序必须保证每个状态只依赖同一天更早的交易阶段或自身旧值；同日零利润买卖不改变最优答案。
解法 1：四状态动态规划
用四个变量记录每个交易阶段结束后的最大现金，逐日按第一次买、第一次卖、第二次买、第二次卖更新。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
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