Simple Python solution, beats 99%

  • 0

    iterate the array, and cumulative subarray sum,

    1. if sub_sum + nums[i] <= nums[i], it means the nums[i] maybe the starter of the maximum subarray
    2. else: nums[i] maybe one of the maximum subarray elements
    3. track the maximum sum
    def maxSubArray(self, nums):
        # (containing at least one number)
        sub_sum, max_sum = nums[0], nums[0]
        for val in nums[1:]:
            if sub_sum + val > val:
                sub_sum += val
                sub_sum = val
            max_sum = max(sub_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.