0123.md

title	description	keywords
123. 买卖股票的最佳时机 III	LeetCode 123. 买卖股票的最佳时机 III题解，Best Time to Buy and Sell Stock III，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 123. 买卖股票的最佳时机 III 买卖股票的最佳时机 III Best Time to Buy and Sell Stock III 解题思路 数组 动态规划

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

🔴 Hard  🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]

Output: 6

Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]

Output: 4

Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

题目大意

给定一个数组，它的第 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. 动态规划： 定义一个三维数组 dp，其中 dp[i][j][0] 表示截至第 i 天、最多进行 j 次交易、不持有股票时的最大利润， dp[i][j][1] 表示示截至第 i 天、最多进行 j 次交易、持有股票时的最大利润。

::: info 状态 j 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 j，那么昨天的最大交易次数上限必须是 j - 1。 :::

2. 状态转移方程：

   • dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])，表示在第 i 天，不持有股票的最大利润等于前一天不持有股票的最大利润，或者前一天持有股票的最大利润加上今天卖出的利润的最大值。

   • dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])，表示在第 i 天，持有股票的最大利润等于前一天持有股票的最大利润，或者前一天不持有股票的最大利润减去今天买入的利润的最大值，今天买入的话，前一天的交易次数上限要减一。

   • 由于 j 的取值范围较小，可以直接把 j = 1、2 的情况全部列举出来也可以：

     • dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
     • dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
     • dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
     • dp[i][1][1] = max(dp[i-1][1][1], -prices[i])

3. 边界条件： 第一天（i == 0）时，dp[0][j][0] = 0，dp[0][j][1] = -prices[0]。

4. 初始化： 初始化利润为 0。

5. 返回最大利润： 最后返回 dp[n - 1][2][0]，即最后一天不持有股票的最大利润，因为若最后一天还持有股票没有卖出，收益肯定小于做了一次交易的情况。

• 时间复杂度: O(n) - 遍历整个二维数组，其中 n 是股票价格数组的长度。
• 空间复杂度: O(n) - 使用了一个 2 * 3 * n 的三维数组来存储中间状态。

---

思路二：动态规划-状态压缩

1. 状态定义：由于 dp[i][...] 只与和 dp[i - 1][...] 有关，且 j 只有两种情况，所以可将 dp 数组简化为四个状态：

   • dp_i20：截至第 i 天、最多交易两次、不持有股票的最大收益;
   • dp_i21：截至第 i 天、最多交易两次、持有股票的最大收益;
   • dp_i10：截至第 i 天、最多交易一次、不持有股票的最大收益;
   • dp_i11：截至第 i 天、最多交易一次、持有股票的最大收益;

2. 状态转移方程：

   • dp_i20 = max(dp_i20, dp_i21 + prices[i])
   • dp_i21 = max(dp_i21, dp_i10 - prices[i])
   • dp_i10 = max(dp_i10, dp_i11 + prices[i])
   • dp_i11 = max(dp_i11, -prices[i])

3. 遍历天数：遍历每一天的股票价格，更新四个状态的值。

4. 返回结果：返回最终的 dp_i20 值，即最大的利润。

复杂度分析

• 时间复杂度: O(n)，只需要遍历一次股票价格数组。
• 空间复杂度: O(1)，只使用了常数个额外的变量。

代码

::: code-tabs @tab 动态规划

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	const n = prices.length;
	const m = 2;
	const dp = new Array(n)
		.fill(0)
		.map(() => new Array(m + 1).fill(0).map(() => new Array(2).fill(0)));
	for (let i in prices) {
		for (let j = m; j >= 1; j--) {
			if (i == 0) {
				dp[0][j][0] = 0;
				dp[0][j][1] = -prices[0];
				continue;
			}
			dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
			dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
		}
	}
	return dp[n - 1][m][0];
};

@tab 动态规划-状态压缩

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
	let dp_i20 = 0,
		dp_i21 = -Infinity,
		dp_i10 = 0,
		dp_i11 = -Infinity;
	for (let price of prices) {
		dp_i20 = Math.max(dp_i20, dp_i21 + price);
		dp_i21 = Math.max(dp_i21, dp_i10 - price);
		dp_i10 = Math.max(dp_i10, dp_i11 + price);
		dp_i11 = Math.max(dp_i11, -price);
	}
	return dp_i20;
};

:::

相关题目

题号	标题	题解	标签	难度	力扣
121	买卖股票的最佳时机	[✓]	数组 动态规划	🟢	🀄️ 🔗
122	买卖股票的最佳时机 II	[✓]	贪心 数组 动态规划	🟠	🀄️ 🔗
188	买卖股票的最佳时机 IV	[✓]	数组 动态规划	🔴	🀄️ 🔗
689	三个无重叠子数组的最大和	[✓]	数组 动态规划	🔴	🀄️ 🔗
2291	最大股票收益 🔒		数组 动态规划	🟠	🀄️ 🔗
2555	两个线段获得的最多奖品		数组 二分查找 滑动窗口	🟠	🀄️ 🔗