Maximum Subarray

题目

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

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray[4,-1,2,1]has the largest sum =6.

思路分析

这道题乍一看应该跟two pointers有关系，因为要找的是一个window，这个window中的数字的和最大。但是这道题有自己的特点，因为如果一个数加上一个正整数，那么和就会变大，如果一个数加上一个负数，那么和就会变小。给予这一特点，我们可以总结出以下的几点：

• 如果array中有正整数，那么和最大的subarray必然是从正整数开始
• 如果array中没有正整数，那么和最大subarray就是最大的那个负数或0
• 如果前面的数的和是负数，那么新的和就要从当前的数开始重新计算，因为之前的和加上现在的数一定比当前的数小，这个就相当于left pointer的移动
• 如果前面的数的和是正数，那么新的和就是前面的数的和加上当前的数

通过上面几点分析，可以得到具体的code实现

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxNum = nums[0]
        sumNum = 0
        for num in nums:
            if sumNum < 0: sumNum = num
            else: sumNum += num
            if sumNum > maxNum: maxNum = sumNum
        return maxNum