53. Maximum Subarray

问题描述

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

O(n)思路

loop一遍，用两个值记录hereMax（某一段的最大值） 和 totalMax（最后return的值）；初始时hereMax = 0, totalMax = MIN_INT

1. hereMax每次加等于新的element，然后和totalMax对比，若大于totalMax，更新totalMax
2. 另外，如果hereMax的值已经小于0了，说明不管后面的element是多少，前面的sum只会让后面的sum变小，所以把前面的sum都舍弃，把hereMax重新assign为0

    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hereMax = 0
        totalMax = -2**31
        for i in nums:
            hereMax += i
            if hereMax > totalMax:
                totalMax = hereMax
            if hereMax < 0:
                hereMax = 0

        return totalMax