53 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.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

The Idea: Only negative elements hurt. As the array get accumulated, if the current sum continues to remain positive, then there is potential for it exceed the current maximum. An otherwise negative element will pull us backwards.

Complexity: O(n) time and O(1) space

import sys


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

        if not nums: return 0

        the_max = -sys.maxsize
        cur_sum = 0
        for num in nums:
            cur_sum += num
            the_max = max(the_max, cur_sum)
            if cur_sum < 0:
                cur_sum = 0

        return the_max