塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-63股票的最大利润-python

《剑指offer》python实现系列,全目录

题目描述

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?例如,一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11。

第一想法:

max(list) - min(list)

不行,要考虑时间,如果【16,11,4,10】最大利润是6

剑指offer方法:

我们不难想到用蛮力法来解决这个问题,也就是找出数组中所有的数对,并逐一求出它们的差值。该算法的时间复杂度是$O(n^2)$ .

我们也可以换一种思路。我们先定义函数 diff(i) 为当卖出价为数组中第 i个数字时可能获得的最大利润。显然,在卖出价固定时,买入价越低获得的利润越大。也就是说,如果在扫描到数组中的第i个数字时,只要我们能够记住之前的 i-1个数字中的最小值,就能算出在当前价位卖出时可能得到的最大利润。基于这种思路的代码如下:`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19


class Solution:
def MaxDiff(self, numbers):
if not numbers or len(numbers) < 2:
return 0;
minnum = numbers[0]
maxDiff = numbers[1] - minnum
for i in range(2, len(numbers)):
if minnum > numbers[i-1]:
minnum = numbers[i-1]
curdiff = numbers[i] - minnum

if curdiff > maxDiff:
maxDiff = curdiff

return maxDiff

Solution().MaxDiff([16,11,4,10])
if help:小手一抖点个广告 or 大手一挥资助一下