代码随想录算法训练营Day 48

算法训练营Day 48"/>

代码随想录算法训练营Day 48

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

力扣题目链接(opens new window)

给定一个数组，它的第 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 <= 10^5
• 0 <= prices[i] <= 10^5

class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0first_buy, first_sell = -float('inf'), 0second_buy, second_sell = -float('inf'), 0for price in prices:first_buy = max(first_buy, -price)first_sell = max(first_sell, first_buy + price)second_buy = max(second_buy, first_sell - price)second_sell = max(second_sell, second_buy + price)return second_sell

假设我们有以下股票价格列表：

prices = [3, 5, 0, 3, 8]

我们将逐步跟踪 first_buy, first_sell, second_buy, second_sell 这四个变量在每一天的值，以理解代码是如何工作的。

初始状态

• first_buy = -inf
• first_sell = 0
• second_buy = -inf
• second_sell = 0

第1天：价格 = 3

• first_buy = max(-inf, -3) = -3 （选择买入，损失3）
• first_sell = max(0, -3 + 3) = 0 （还没卖出，没有利润）
• second_buy = max(-inf, 0 - 3) = -3 （在第一次卖出后再买入，损失3）
• second_sell = max(0, -3 + 3) = 0 （还没进行第二次卖出，没有利润）

第2天：价格 = 5

• first_buy = max(-3, -5) = -3 （保持第一天买入的状态）
• first_sell = max(0, -3 + 5) = 2 （如果在这天卖出，利润为2）
• second_buy = max(-3, 2 - 5) = -3 （保持第一天的第二次买入状态）
• second_sell = max(0, -3 + 5) = 2 （如果在这天进行第二次卖出，利润为2）

第3天：价格 = 0

• first_buy = max(-3, -0) = -3 （保持之前的买入状态）
• first_sell = max(2, -3 + 0) = 2 （保持之前的卖出状态）
• second_buy = max(-3, 2 - 0) = -1 （如果在这天买入，损失减少）
• second_sell = max(2, -1 + 0) = 2 （保持之前的卖出状态）

第4天：价格 = 3

• first_buy = max(-3, -3) = -3
• first_sell = max(2, -3 + 3) = 2
• second_buy = max(-1, 2 - 3) = -1
• second_sell = max(2, -1 + 3) = 2

第5天：价格 = 8

• first_buy = max(-3, -8) = -3
• first_sell = max(2, -3 + 8) = 5 （如果在这天卖出第一次买入的股票，利润为5）
• second_buy = max(-1, 5 - 8) = -1
• second_sell = max(2, -1 + 8) = 7 （如果在这天卖出第二次买入的股票，利润为7）

最终，second_sell 的值为 7，这是按照这个策略可以获得的最大利润。这意味着最佳策略是在第一天价格为3时买入，然后在第五天价格为8时卖出，利润为5；同时，如果我们在第三天价格为0时再次买入，然后同样在第五天价格为8时卖出，额外利润为8，总利润为7。

188.买卖股票的最佳时机IV

力扣题目链接(opens new window)

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

• 示例 1：

• 输入：k = 2, prices = [2,4,1]

• 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

• 示例 2：

• 输入：k = 2, prices = [3,2,6,5,0,3]

• 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:if not prices:return 0n = len(prices)if k >= n // 2:# 如果 k 大于 n/2，就变成了无限次交易的情况return self.maxProfit_inf(prices)dp = [[0] * (k + 1) for _ in range(n)]for j in range(1, k + 1):max_buy = -prices[0]for i in range(1, n):dp[i][j] = max(dp[i-1][j], prices[i] + max_buy)max_buy = max(max_buy, dp[i-1][j-1] - prices[i])return dp[-1][-1]def maxProfit_inf(self, prices):profit = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]:profit += prices[i] - prices[i-1]return profit

优化：当 k 大于 n/2（股票价格数组的一半）时，问题变成了可以进行无限次交易的情况。这种情况下，只需简单地在价格上升时买入，在价格下降前卖出即可。这是因为在价格上升的每一步都可以视为一次独立的交易。

这个问题的核心在于理解为什么当 `k`（允许的最大交易次数）大于 `n/2`（其中 `n` 是给定的股票价格数组的长度）时，问题就变成了可以进行无限次交易的情况。这里的关键在于理解股票交易的基本规则和动态规划的限制。

在股票交易中，一次完整的交易包括一次买入和一次卖出。要使利润最大化，理想的情况是在每次股价上涨前买入，在上涨后卖出。但是，如果交易次数有限，我们就不能捕捉到每一次上涨。

当 `k` 的值很大，尤其是当它大于 `n/2` 时，情况就变了。考虑到每一次完整交易至少需要两天（一天买入，一天卖出），所以在最极端的情况下，最多也只能进行 `n/2` 次交易（比如在股价连续上涨的情况下，第一天买入，第二天卖出，如此反复）。

当 `k >= n/2` 时，实际上交易次数的限制就变得没有意义了，因为你已经有足够多的交易次数去捕捉几乎每一次可能的利润了。这就相当于允许了“无限次”交易，因为你不太可能超过这个次数的限制。在这种情况下，你只需要关注价格上涨的部分，每次上涨都买入卖出，来获取最大利润。

所以，在这个特定的场景下，算法的复杂度可以降低，我们不再需要考虑复杂的动态规划策略，而是简单地累加所有上升趋势的利润。这就是代码中 `maxProfit_inf` 函数的作用。