Python O(n) solution


  • 0
    class Solution(object):
        def maxSubArray(self, nums):
            sumsofar, minim, ans = [ 0 for i in xrange(len(nums) + 1) ], 0, -0xffffffff
            for i in xrange(1, len(nums) + 1):
                sumsofar[i] = nums[i - 1] + sumsofar[i - 1]
                ans = max(ans, sumsofar[i] - minim)
                minim = min(minim, sumsofar[i])
            return ans
    

  • 0
    R

    The space complexity in this case is O(n) as well.


Log in to reply
 

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