leetcode：买股票的最大收益问题

题目：一个数组代表股票每天的价格，可以选择从某一天买入，然后之后的一天卖出，求能够获得的最大收益。

例题：输入

[3,4,5,6,5,8]，

输出为5（在价格为3的时候买入，在价格为8的时候卖出）

输入为

[3,4,5,6,7,2,8]

输出为6（在价格为2时买入，在价格为8时卖出）

思路：就是求出前序列的最小值，以及后序列的最大值，得到的差值就是我们要的答案

首先想到的是暴力求解：

def solution(array):
    temp=0
    result=0
    max_out=0
    for i in range(len(array)-1):
        for j in range(i+1,len(array)):
            temp=array[j]-array[i]
            if temp>max_out:
                max_out=temp
    return(max_out)

就是求出所有的子序列，然后求出最大差值，更新。

方法2：

可以求出序列两两之间的差值，然后开始累加，如果累加和为负数，说明这不是最佳适合的买入点，可以清零，从后继续开始，找到累加和的最大值，更新即可。

def our_solution(self,array):
    max_out=0
    temp=0
    for i in range(1,len(array)):
        temp+=array[i]-array[i-1]
        if temp>max_out:
            max_out=temp
        elif temp<0:
            temp=0
    return max_out

这样遍历的时间复杂度为0（n），空间复杂度为0（1）