题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

求解数列中连续子序列的最大和。

For example：
给定数组， [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和最大 sum = 6。

思路方法

sum 标记的是 index 之前的数组之和，maxsum 是标记到 index 为止，连续数组的最大和。
如果 sum < 0，则直接放弃前面的连续值，因为负数不会对最大值做出贡献；如果 sum >= 0，则继续累加。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)

        if size == 1:
            return nums[0]

        sum = nums[0]
        maxsum = nums[0]

        #注意，这里 index 是从 1 开始的，因为在上面的代码，0 我已经初始赋过值了
        for index in range (1, size):
            if sum >= 0:
                sum = sum + nums[index];
            else:
                sum = nums[index];
            if sum > maxsum:
                maxsum = sum

        return maxsum