Python 46ms O(N) with optimization


  • 0
    J

    Not very short or pleasant answer, but with an optimization step that I haven't seen (or maybe I missed) in other solutions. I put the ideas in comments in the code below and here as well: once the sum drops to 0, search for the next positive number (instead of doing the plus negative numbers..).

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            out = max(nums)
            if out<=0: ## if all negative numbers, return the max
                return out
            if min(nums)>=0: ## if all positive number, return the sum
                return sum(nums)
            while nums[-1]<=0:## remove trailing negative num.
                nums=nums[:-1]
            n=len(nums)
            if n==1: ## if only 1 number, return
                return nums[0]
            iout=0
            i=0
            while i<n:
                iout+=nums[i]
                if nums[i]<0 and iout <0: ## *** if sum drops to 0 and current number is negative, reset sum to 0 and find the next positive number
                    iout=0
                    while nums[i]<0:
                        i+=1
                    continue
                if iout>out:
                    out=iout
                i+=1
            return out
    

Log in to reply
 

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