python 两种解法

解法一:暴力递归
思路:列出所有可能的子数组和，然后选取最大值

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if len(array) == 1:
            return array[0]
        result = []
        res = 0
        for i in array:
            res += i
            result.append(res)
        num = self.FindGreatestSumOfSubArray(array[1:])
        result.append(num)
        return max(result)

解法二:
动态规划

把子树和抽象的拆分成两个部分，即当前结点和前一个结点的最大子数和

F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max（F（i-1）+array[i] ， array[i]）
res：所有子数组的和的最大值
res=max（res，F（i））

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return 0
        # res 不能和num一样设置为0，否则在给定数组全部为负的情况下将会出错
        res = None
        num = 0
        for i in range(len(array)):
            num = max([num+array[i], array[i]])
            # 第0个数的最大子树和为其本身
            if not res:
                res = num
            res = max([num, res])
        return res