O(n) python solution with explanation


  • 0
    C
    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums: return 0
            
            cur_sum = nums[0]   # max sum of sub_array nums[:i]
            max_sum = cur_sum   # result
            for i in range(1, len(nums)):
                # nums[i] is the next number to read
                # if current sum is negative, nums[i]+cur_sum < cur_sum,
                # so update the cur_sum to nums[i].
                # Update the cur_sum to nums[i]+cur_sum otherwise.
                cur_sum = nums[i] if cur_sum < 0 else nums[i]+cur_sum
                max_sum = max(cur_sum, max_sum)
            return max_sum
    

Log in to reply
 

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