剑指 最大子序列和

当以n-1元素结尾最大子序列和为负数时，以n结尾最大子序列和是第n个元素，否则为全部加和。
注意循环条件为（1,len(array)）和(1,len(array)+1)的不同

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        max_value=[0]*(len(array))
        result=array[0]
        max_value[0]=array[0]
        if len(array)==0:
            return 0
        for i in range(1,len(array)):
            max_value[i]=max(0,max_value[i-1])+array[i]
            result=max(result,max_value[i])
        return result

节省空间，只需记住前一个n-1的最大值 即可

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        max_value=[0]*(len(array))
        result=float('-inf')
        premax_value=array[0]
        if len(array)==0:
            return 0
        for i in range(1,len(array)):
            max_value=max(0,premax_value)+array[i]
            premax_value=max_value
            result=max(result,max_value)
        return result