53_maximum_subarray.py

'''
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.
'''
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_sum = 0
        result = -9999999999
        for n in nums:
            cur_sum = max(n, cur_sum+n)
            result = max(result, cur_sum)
        return result