网易面试题:一组股票价格,找出买点和卖点,使得利润最大

一 用python实现一次买入和卖出

1.时间复杂度为o(n^2)的方法

# import matplotlib as mpl

# import matplotlib.pyplot as plt

# pip install matplotlib

import mathfrom BuySellPair 

import BuySellPairfrom Point 

import Pointy = []

for x in range(0, 60):    y.append(math.sin(math.pow(x - 35, 2) / 100) * (x - 35))

# plt.figure(1)

# plt.plot(x, y)

# plt.show()

# 最大值记为max

benefit = 0buy = 0sell = 0

# 先在函数内 遍历每一个点（第一层循环）作为买入点

# 找到该点之后，任意一个点（卖出店）与该点的差值（盈利），并与max比较，比max大则标记下来

for i in range(0, len(y)):    before = y[i]    for j in range(i, len(y)):        after = y[j]        dy = after - before        if benefit < dy:            benefit = dy            buy = i            sell = jprint("买入点为%s，卖出点位%s，获利：%s" % (buy, sell, benefit))

2.时间复杂度为O(n)的方法

pare = BuySellPair()

pare.benefit = 0

minPricePoint = Point()

for i in range(1, len(y)):    benefit_temp = y[i] - pare.buy.y    

if benefit_temp > pare.benefit:        

pare.sell = Point(i, y[i])        

pare.benefit = benefit_temp    

if y[i] < minPricePoint.y:        

minPricePoint = Point(i, y[i])    

possible_max = y[i] - minPricePoint.y    

if possible_max > pare.benefit:        pare.sell = Point(i, y[i])        pare.benefit = possible_max        pare.buy = minPricePointprint(pare) 

二.用js实现

1.时间复杂度为O(n)的方法