A very neat O(n) solution just 7 lines

  • 1

    the solution is much simpler than what I think it should be.
    maxcur is the max sum ending with the current element.
    maxsum is the final max return value. enjoy.
    initialize above with -infinity to avoid boundary check.

    class Solution(object):
        def maxSubArray(self, nums):
            maxsum = maxcur = -float("inf")
            for i in nums:
                maxcur = max(i, maxcur+i)
                maxsum = max(maxsum, maxcur)
            return maxsum

Log in to reply

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