剑指offer面试题----连续子数组的最大和

题目：输入一个整型数组,数组里有整数也有负数。
数组中一二或连续的多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)

思路：动态规划，分别计算第i时刻（0<=i<=n）之前子数组的最大和，如果第i-1时刻的值为负值，则将其丢弃，则当前最大和为当前数组位置的值，若不为负数，则将其加上当前位置的值。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        alist = [0]*len(array)
        
        for i in range(len(array)):
            if i==0 or alist[i-1]<0:
                alist[i] = array[i]
            else:
                alist[i] = alist[i-1] + array[i]
        return max(alist)