❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股价 = 0）的时候买入，在第 6 天（股价 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。
随后，在第 7 天（股价 = 1）的时候买入，在第 8 天（股价 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
方法一：动态规划
解题步骤
- 定义状态：
dp[i][j]表示第i天完成j笔交易的最大利润。 - 初始化状态：
dp[0][1]和dp[0][2]都初始化为负无穷，表示不可能完成交易。 - 状态转移：
- 第
i天完成一笔交易的最大利润：dp[i][1] = max(dp[i-1][1], -prices[i]) - 第
i天完成两笔交易的最大利润：dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
- 结果输出：
max(dp[n-1][1], dp[n-1][2])
Python 示例
def maxProfit(prices): n = len(prices) if n == 0: return 0 dp = [[0] * 3 for _ in range(n)] dp[0][1] = -prices[0] dp[0][2] = float('-inf') for i in range(1, n): dp[i][1] = max(dp[i-1][1], -prices[i]) dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]) return max(0, dp[n-1][2]) # Example usage prices = [3,3,5,0,0,3,1,4] print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(N)，用于存储 dp 数组。
算法图解与说明
初始: dp = [[-3, -inf], [0, 0], [0, 0], ...] 第一天: 不操作，买入 -3 第二天: 不操作，维持 -3 第三天: 不操作，维持 -3 第四天: 不操作，买入 0 第五天: 不操作，维持 0 第六天: 卖出 +3 第七天: 买入 1 第八天: 卖出 +4
方法二：状态机优化
解题步骤
- 使用四个变量表示不同状态下的最大利润：
buy1,sell1,buy2,sell2。 - 初始状态设为：
buy1 = buy2 = -inf,sell1 = sell2 = 0。 - 更新状态机：
buy1: 第一次买入的最大利润sell1: 第一次卖出的最大利润buy2: 第二次买入的最大利润sell2: 第二次卖出的最大利润
Python 示例
def maxProfit(prices): buy1, sell1, buy2, sell2 = float('-inf'), 0, float('-inf'), 0 for price in prices: buy1 = max(buy1, -price) sell1 = max(sell1, buy1 + price) buy2 = max(buy2, sell1 - price) sell2 = max(sell2, buy2 + price) return sell2 # Example usage prices = [3,3,5,0,0,3,1,4] print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)
- 空间复杂度：O(1)
算法图解与说明
状态更新过程： 初始: buy1 = -inf, sell1 = 0, buy2 = -inf, sell2 = 0 价格迭代: 3 -> buy1 = -3 3 -> sell1 = 0 5 -> sell1 = 2 0 -> buy2 = 2 0 -> 维持 3 -> sell2 = 5 1 -> 维持 4 -> sell2 = 6
这两种方法为买卖股票问题的高级解法，适用于有多次交易机会的场景。
方法三：左右扫描数组法
解题步骤
- 使用两个数组
left_profits和right_profits。left_profits[i]存储从第一天到第i天的最大利润，right_profits[i]存储从第i天到最后一天的最大利润。 - 从左到右遍历一遍股价数组，更新
left_profits为到当前日为止的最大利润。 - 从右到左遍历股价数组，更新
right_profits为从当前日到结束的最大利润。 - 最终结果为某一天两边利润之和的最大值。
Python 示例
def maxProfit(prices): n = len(prices) if n <= 1: return 0 left_profits = [0] * n right_profits = [0] * n # 左侧最小值初始化 min_price = prices[0] for i in range(1, n): left_profits[i] = max(left_profits[i-1], prices[i] - min_price) min_price = min(min_price, prices[i]) # 右侧最大值初始化 max_price = prices[n-1] for i in range(n-2, -1, -1): right_profits[i] = max(right_profits[i+1], max_price - prices[i]) max_price = max(max_price, prices[i]) # 计算两边利润的最大和 max_profit = 0 for i in range(n): max_profit = max(max_profit, left_profits[i] + right_profits[i]) return max_profit # Example usage prices = [3,3,5,0,0,3,1,4] print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，其中 N 是数组的长度。
- 空间复杂度：O(N)，需要两个长度为 N 的数组来存储左右两侧的最大利润。
算法图解与说明
股票价格: [3, 3, 5, 0, 0, 3, 1, 4] 左侧利润: [0, 0, 2, 2, 2, 2, 2, 2] 右侧利润: [3, 3, 3, 3, 3, 3, 3, 0] 最大利润: 每天两侧利润之和的最大值为 6 (第 6 天)
方法四：改进的状态机方法
解题步骤
- 减少状态机方法中变量的使用，只使用两个变量跟踪到目前为止的最大利润。
- 遍历价格数组时，更新四个关键状态：第一次买入、第一次卖出、第二次买入和第二次卖出的最大利润。
- 通过逐步更新这四个状态来最大化最终的利润。
Python 示例
def maxProfit(prices): first_buy, first_sell = float('-inf'), 0 second_buy, second_sell = float('-inf'), 0 for 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 # Example usage prices = [3,3,5,0,0,3,1,4] print(maxProfit(prices)) # Output: 6
算法分析
- 时间复杂度：O(N)，N 是股票价格数组的长度。
- 空间复杂度：O(1)，使用常数空间。
算法图解与说明
初始状态: first_buy = -inf, first_sell = 0, second_buy = -inf, second_sell = 0 更新过程: - 第1天: first_buy 更新为 -3 - 第2天: 无变化 - 第3天: first_sell 更新为 2 - 第4天: second_buy 更新为 2 - 第5天: 无变化 - 第6天: second_sell 更新为 5 - 第7天: 无变化 - 第8天: second_sell 更新为 6
以上四种方法各有优势，适用于不同的场景和优化需求。可以根据具体需要选择最合适的解决方案。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
