剑指offer：连续多个整数组成一个子数组，求所有子数组的和的最大值

一、问题描述

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

二、代码实现

对第一个数进行判断，大于0才开始计入。

主要思想动态规划，就是如果前一个数大于0，那么就加上。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return None
        maxNum = array[0]
        for i in range(1,len(array)):
            if array[i-1] > 0:
                array[i] = array[i-1] + array[i]
            maxNum = max(maxNum, array[i])
        return maxNum