fast python O(n) time, const space


  • 0
    W

    cur is an accumulator. To find the max subarray only positive accumulator matters, so just reset when it becomes negative
    '''

    def maxSubArray(self, nums):
        largest = cur = nums[0]
        for i in range(1, len(nums)):
            if cur < 0: cur = 0
            cur += nums[i]
            largest = max(cur, nums[i], largest)
        return largest
    

    '''


Log in to reply
 

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