算法训练营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` 函数的作用。
更多推荐
代码随想录算法训练营Day 48
发布评论