LeetCode122（买卖股票最佳时机II）
每日一题——LeetCode122（买卖股票最佳时机II）
https://www.bilibili.com/video/BV11r4y1W7qS
题意
range(1,5)表示1,2,3,4即[1,5)
难度：中等
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。 返回 你能获得的 最大 利润 。
思路
这里采用贪心算法：
这里等同于每天买卖股票，实现最大利润。
只需要我们每天收集整理正利润即可，收集正利润的区间就是股票买卖点区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润是贪心算法所“贪”的地方。
局部最优：收集每天正利润
全局最优：求最大利润
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
tmp = prices[i] - prices[i - 1]
if tmp > 0:
profit += tmp
return profit代码实现
我的解法：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
if len(prices)==1:
return 0
z=0
for i in range(1,len(prices)):
j=prices[i]-prices[i-1]
if j>0:
z+=j
return z
#时间复杂度O(n)
#空间复杂度O(1)
img
错误写法：想法对了，但是使用双重循环，是用每一项减去剩去第二层循环的每一项。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
z=0
for j in prices:
for i in prices[1:]:
y=j-i
if y>0:
z+=y
return z每天一题，神清气爽！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
