# Python 46ms O(N) with optimization

• 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
``````

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