“This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6.Copy the code

Example 2:

Input: nums = [1] Output: 1Copy the code

Example 3:

Input: nums = [5,4,-1,7,8Copy the code

Tip:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Their thinking

In order to solve the divide-and-conquer problem, we need to use a kind of advanced data structure field tree, and we have reached the optimal solution (time complexity O(n), space complexity O(1)). Most of the interval sum problems are solved by prefixes and arrays. For those of you who don’t know prefixes and arrays, let’s talk about prefixes and arrays.

Prefixes and arrays

A prefix and an array is each entry in an array equal to the sum of the current position and previous elements in the array. For example, the original array is [1,2,3,4] and the prefix and array are [0,1,3,6,10]. Note that prefixes and arrays default to 0 in the first digit, so the prefix and array will be +1 longer than the original array. Why do we have a leading 0?

  1. Easy to calculate the prefix and the first item of the array. Because when we evaluate the prefix and the value of the current item in the array, we just need to add the value of the previous item to the value of the element in front of the original array, so in order to evaluate the first element in the original array with the value of the previous item, we need a prefix0.
  2. Easy to calculate intervals and values. If you look at prefixes and arrays, you can see that the following value minus the preceding value is exactly the same as the sum of the elements in the interval in the original array. So each term minus the top term0That’s just subscript from the original array0The interval and value to the current position (note here, because there is a prefix0, so the prefix and the index in the array are equal to the index in the original array+ 1).

Using prefixes and arrays, we can easily find the sum of the elements in a certain range, which is the subarray sum in this case. So we can iterate over prefixes and arrays, recording the minimum value in the preceding range, subtracting the minimum value in the preceding range from the current value, and we get the largest subarray and value that we can get at the end of the current position. I then try to update the result value with that result, and I end up with the largest subarray sum in the array. Note that during this process, you also need to try to update the minimum with the prefix and result of the current location to ensure that the minimum holds the minimum value of the processed interval.

The demo

Code implementation

Var maxSubArray = function(nums) {sum = 0, sum = 0, // The sum of the largest subarray is negative Infinity Max = -infinity; // iterate over the input array for(let I = 0; i<nums.length; Sum ++){sum += nums[I]; sum += nums[I]; sum += nums[I] Math.max(Max,sum-min)} return Max; math.max (Max,sum-min); };Copy the code

At this point we are done with leetcode-53- maximum subarray sum

If you have any questions or suggestions, please leave a comment!