Topic describes

Enter an array of integers. One or more integers form a subarray. Find the maximum sum of all subarrays. The time complexity is O(n).

Example 1: input: nums = [- (2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.

Their thinking

The main thing about this problem is to keep time O(n)

  1. We’re going to evaluate the sum of the previous items plus the current item,
  2. And then comparing the last result with our first judgment result, we can get the maximum value
  3. If nums[0] is assigned and index=1 is iterated, we can directly handle the case where nums has only one value

The sample code

def maxSubArray(self, nums: List[int]) - >int:
    add = nums[0]
    res = add
    for i in range(1.len(nums)):
        item = nums[i]
        add = max(item, add + item)
        res = max(res, add)
    return res
Copy the code