fast python O(n) time, const space

  • 0

    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.