LeetCode：3573.买卖股票的最佳时机 V

状态机建模#

在 188.买卖股票的最佳时机 IV 的 $k$ 次交易中，我们每一轮交易只有“持有”和“不持有”两种状态。但在这一题里，当我们正处于一笔交易中时，身份有两种可能：

1. 正向持有：先买了，手里拿着股票等卖。
2. 反向持有：先卖了，手里攥着钱等跌了买回来。
3. 空仓：手里既没股票也没欠钱，准备开始第 $j$ 次交易。

所以，对于第 $j$ 次交易（$1 \le j \le k$），我们定义三个变量：

• buy[j]：第 $j$ 次交易中，处于买入后的状态（正向持股）。
• shorting[j]：第 $j$ 次交易中，处于卖出后的状态（反向做空）。
• sell[j]：第 $j$ 次交易已完成的状态（无论是普通还是做空）。

状态转移方程#

当处于第 $j$ 次交易中，当天的股票价格为 $P$：

• 正向持有（buy[j]）
  • 来源 A：昨天就正向持有
  • 来源 B：昨天结束时处于空仓状态，今天买入
  • $buy[j] = max(buy[j], sell[j = 1] - p)$
• 反向持有（shorting[j]）
  • 来源 A：昨天就反向持有
  • 来源 B：昨天 结束时处于空仓状态，今天卖出
  • $shorting[j] = max(shorting[j], sell[j - 1] + p)$
• 空仓（sell[j]）
  • 来源 A：昨天 结束时处于空仓
  • 来源 B：昨天正向持有，今天卖出
  • 来源 C：昨天反向持有，今天买入
  • $sell[j] = max(sell[j], buy[j] + p, shorting[j] - p)$

代码实现#

因为题目中规定“你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作”，所以这里使用倒序遍历会更方便。

public long maximumProfit(int[] prices, int k) {
	long[] buy = new long[k + 1];
	long[] shorting = new long[k + 1];
	long[] sell = new long[k + 1];

	Arrays.fill(buy, Long.MIN_VALUE / 2);
	Arrays.fill(shorting, Long.MIN_VALUE / 2);

	for (int p : prices) {
		for (int j = k; j >= 1; j--) {
			// 此时的 buy[j] 和 shorting[j] 还是昨天的状态
			sell[j] = Math.max(sell[j], Math.max(buy[j] + p, shorting[j] - p));

			// 因为是倒序，此时的 sell[j-1] 还没有被今天的新价格更新过
			buy[j] = Math.max(buy[j], sell[j - 1] - p);
			shorting[j] = Math.max(shorting[j], sell[j - 1] + p);
		}
	}
	return sell[k];
}