给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
来源:力扣(LeetCode)
具体的解题思路如下:
代码如下:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n < 2: return 0
dp = [[0,0] for i in range(n)] #dp的初始化
dp[0][0] = 0 #第0天不持股自然就为0了
dp[0][1] = -prices[0] #第0天持股,那么价格就是-prices[0]了
#第1天不持股,要么第0天就不持股,要么就是第0天持股,然后第1天卖出
dp[1][0] = max(dp[0][0],dp[0][1]+prices[1])
#第一天持股,要么就是第0天就持股了,要么就是第0天不持股第1天持股
dp[1][1] = max(dp[0][1],dp[0][0]-prices[1])
for i in range(2,n):
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])
return dp[-1][0]
文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890
Python Free
邮箱:417803890@qq.com
QQ:417803890
皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved
微信扫一扫关注公众号:
Python Free