Python O(n) solution with explanation


  • 0
    T
    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums)==0:
                return None
            #Initialize the max sum with 1st int, as it may be negative
            res,pre_sum=nums[0],nums[0]
            for i in range(1,len(nums)):
                #start the new array from nums[i] if the max sub ending with nums[i-1] is negative
                cur_sum=nums[i]+pre_sum if pre_sum>0 else nums[i]
                #update the max sub ending with nums[i]
                pre_sum=cur_sum
                #cmp with previous max sub
                res=max(res,cur_sum)
            return res
    

Log in to reply
 

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