Simple Python O(n) algorithm


  • 0
    C

    Here's a simple python code for this question:

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 0:
                return(0)
            minSofar = min(nums[0], 0)
            maxSofar = nums[0]
            cumsum = nums[0]
            for i in range(1, len(nums)):
                cumsum += nums[i]
                maxSofar = max(maxSofar, cumsum - minSofar)
                minSofar = min(minSofar, cumsum)
            return(maxSofar)
    

    Basically, we are scanning the list and maintain the minimum cumsum that we have seen, and constantly update the max cumsum - the min cumsum occured before to compute the max sum for subarrays.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.