83.股票的最大利润
题目描述:
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖 一次 该股票可能获得的利润是多少?
例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。
如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11。
样例:
```
输入:[9, 11, 8, 5, 7, 12, 16, 14]
输出:11
```
思路1:
从左到右扫描数组,每次会出现三种情况:
1、若当前值比已记录的最大值大,则更新最大值
2、若当前值比已记录的最小值小,则将最大值变为0,并更新最小值。(此处更新最大值为0是因为以当前值为分割点的前一段时间的最大利润已经计算出来了)
3、若当前的值位于最大值和最小值之间,则不用更新最大最小值
代码如下:
class Solution(object):
def maxDiff(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
min = 10**9
large = 0
res = 0
for num in nums:
if num > large:
large = num
if num < min:
min = num
large = 0
res = max(res, large-min)
return res
思路2:
从左到右扫描数组,用一个变量minv存储前i个中的最小值,然后更新结果res=max(res, nums[i]-minv)
class Solution(object):
def maxDiff(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
minv = float('inf')
for i in range(len(nums)):
minv = min(minv, nums[i])
res = max(res, nums[i] - minv)
return res