O(n) Python solution


  • 0
    H
    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = len(nums)
            if n == 0:
                return 0
            max_sum, cur_sum = -2**31, 0
            i, j = 0, 0
            while i < n and j < n:
                cur_sum += nums[j]
                max_sum = max(cur_sum, max_sum)
                if cur_sum < 0: # it means sum(nums[i:j+1])<0, so we can skip this segment
                    j += 1
                    i = j
                    cur_sum = 0
                else:    
                    j += 1
            
            return max_sum
    

Log in to reply
 

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