LeetCode：123. 买卖股票的最佳时机 III（python）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode：123. 买卖股票的最佳时机 III（python），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2198字，纯文字阅读大概需要4分钟。
内容图文
LeetCode：123. 买卖股票的最佳时机 III（python）
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
思路：
最多一次交易的动态规划，dp[i] = max(dp[i-1], dp[i] - dp[j])，0<=j<=i
- 第
i天的最大收益 =max（第i-1天的收益，第j天买入第i天卖出的收益）- 若为第一种情况，表示未进行交易
- 若为第二种情况，表示进行交易且收益大于前一天的最大收益；
dp[j]为第i天之前的最低股票值。
最多两次交易的动态规划：dp[t][i] = max(dp[t][i-1], prices[i]-min_p)
- 第
t次交易第i天的最大收益 =max（第t次交易第i-1天的收益，第i天卖出的股票收益-第i天之前的最小负收益） - 考虑最多一次交易的动态规划中
dp[j]为第i天之前买入股票的最低值，即最小值，则min_p也为第i天之前的最小值，但要加入之前交易次数的影响。由于买入股票为负收益，而第i-1天的上次交易后的最大收益为dp[t-1][i-1]，因此最小值min(min_p, prices[i]-dp[t-1][i-1])。 - 由于
min_p为第i天之前的最小值，则可通过一次遍历，同步计算min_p和dp[t][i]。
附代码（Python）：
class Solution:
def maxProfit(self, prices):
if not prices:
return 0
n = len(prices)
dp = [[0]*n for _ in range(3)]
for t in range(1, 3):
min_p = prices[0] # 初始化最小负收益，即买入初始股票
for i in range(1, n):
min_p = min(min_p, prices[i]-dp[t-1][i-1]) # 更新最小负收益
dp[t][i] = max(dp[t][i-1], prices[i]-min_p) # 更新当前交易次数下第 i 天的最大收益
return dp[-1][-1]
test = Solution()
prices_li = [[3,3,5,0,0,3,1,4], [1,2,3,4,5]]
for prices in prices_li:
print(test.maxProfit(prices))
6
4
内容总结
以上是互联网集市为您收集整理的LeetCode：123. 买卖股票的最佳时机 III（python）全部内容，希望文章能够帮你解决LeetCode：123. 买卖股票的最佳时机 III（python）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。