在html中做网站 视频,网络公司网页设计,商城系统 WordPress,公司网站建设计划❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣#xff01; 推荐#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航#xff1a; LeetCode解锁100… ❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣 推荐数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航 LeetCode解锁1000题: 打怪升级之旅每题都包括3-5种算法以及详细的代码实现刷题面试跳槽必备漫画版算法详解通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读看一遍就掌握python源码解读解读python的源代码与调用关系快速提升代码质量python数据分析可视化企业实战案例企业级数据分析案例与可视化提升数据分析思维和可视化能力程序员必备的数学知识与应用全面详细的介绍了工程师都必备的数学知识 期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️ 题目描述
在《买卖股票的最佳时机 II》这个问题中你拥有一个数组其中第 i 个元素是第 i 天给定股票的价格。你可以尽可能进行多次的买卖交易即买一次和卖一次构成一对交易。然而你不能同时参与多笔交易你必须在再次购买之前出售掉之前的股票。
任务是设计一个算法来找出最大利润。你需要考虑在哪些日子买入和卖出能够获得最大利润。
示例
给定价格数组 [7,1,5,3,6,4]最大利润计算方式如下
在价格为1时买入在价格为5时卖出利润为4。在价格为3时买入在价格为6时卖出利润为3。
因此总利润为4 3 7。
注意你不能在买入股票的同一天卖出也不能在买入之前卖出股票。你的目标是最大化总利润。
方法一贪心算法
解题步骤
初始化总利润为0。遍历价格数组从第一天到最后一天。对于每一天如果当天的价格比前一天高计算这两天的利润并累加到总利润中。最后返回总利润。
Python 示例
def maxProfit(prices):total_profit 0for i in range(1, len(prices)):if prices[i] prices[i - 1]:total_profit prices[i] - prices[i - 1]return total_profit算法分析
时间复杂度O(n)其中 n 是价格数组的长度因为我们需要遍历整个数组。 空间复杂度O(1)只需要常数的空间来存储利润等变量。
算法图解
价格数组: [7, 1, 5, 3, 6, 4]
利润计算:
- 买入 1卖出 5利润 4
- 买入 3卖出 6利润 3
总利润: 4 3 7方法二动态规划
解题步骤
创建两个列表cash 和 hold其中 cash[i] 表示第 i 天结束时手上没有股票的最大利润hold[i] 表示第 i 天结束时手上持有股票的最大利润。初始化 cash[0] 0 和 hold[0] -prices[0]。遍历从第 1 天到最后一天更新 cash 和 hold 的值 cash[i] max(cash[i-1], hold[i-1] prices[i])hold[i] max(hold[i-1], cash[i-1] - prices[i]) 最后cash[-1] 将是最大利润。
Python 示例
def maxProfit(prices):if not prices:return 0n len(prices)cash, hold [0] * n, [0] * nhold[0] -prices[0]for i in range(1, n):cash[i] max(cash[i-1], hold[i-1] prices[i])hold[i] max(hold[i-1], cash[i-1] - prices[i])return cash[-1]算法分析
时间复杂度O(n)我们只需要遍历一次股价数组。 空间复杂度O(n)我们需要额外的空间来存储过程中的状态。
算法图解
价格数组: [7, 1, 5, 3, 6, 4]
cash: [0, 0, 4, 4, 7, 7]
hold: [-7, -1, -1, -1, -1, -1]
最终最大利润: 7应用示例
如果给定一个价格数组 [7, 1, 5, 3, 6, 4]使用上述任一方法你都能得到最大利润7。这表明无论是采用贪心策略还是动态规划方法都可以有效地解决问题。 如果觉得这篇文对你有帮助的话记得一键三连关注、赞、收藏是对作者最大的鼓励非常感谢 ❥(^_-) ❤️❤️作者知识有限如有错误请各位大佬评论区批评指正不胜感激❥(^_-)
