问题链接
https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/572/
解题思路
思路一:两次遍历寻找前后两个数的最大差值,发现超时,时间复杂度O(n^2)
思路二:遍历一次,迭代更新最小值,并计算最小值与最新遍历点的差值,最大的即为最大交易
代码(思路二)
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
maxprofit = 0
if len(prices) == 0:
return maxprofit
low = prices[0]
for i in range(1, len(prices)):
if prices[i] < low:
low = prices[i]
else:
profit = prices[i] - low
if maxprofit < profit:
maxprofit = profit
return maxprofit
网友评论