This is the 26th day of my participation in the First Challenge 2022

The title

53. Maximum subarray sum

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

Train of thought

  • As a general rule, we can enumerate each possibility with a double for loop, and then maintain a space of prefixes and two-dimensional arrays that record the sum of the elements from I to j;

  • However, in fact, when we solve these maximal sums, most problems can be done by greedy, the so-called greedy, is to keep the sum of the front part as big as possible;

  • For example, if the first element is 3, and we add up, and the second element is -2, do we add it? And the answer is yes, because 3 minus 2 is greater than 0, and as long as the first part is greater than 0 we add up, and as long as the first part is less than 0 we start from the beginning, and then we judge the sum of each sum, and we take the maximum of the sum as our answer;

    For example: [3, -2, 3]

    - Initial value: prefix prev is 0, maximum value result is the minimum number - In the first round: prefix accumulation becomes 3, the maximum value is the original value and the maximum value of the current prefix is 3 - in the second round: prefix accumulation becomes 1, the maximum value is the original value and the maximum value of the current prefix is 3 - in the third round: The sum of the prefixes becomes 4, and the maximum value of the original and the current prefix is 4Copy the code

    A lot of people, when they encounter -2, will want to start from 0 to calculate again, which is a mistake that is easy to fall into this problem.

  • In this case, we only need one iteration to find the answer we want, and the space is O(1).

implementation

/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function(nums) {
    // Record the prefix
    let prev = 0;
    // Record the maximum value
    let result = Number.MIN_SAFE_INTEGER;

    // A loop, enumerating the result
    for (let i = 0; i < nums.length; i++) {
        // The current maximum prefix plus the current value compared to our previous maximum
        result = Math.max(result, nums[i] + prev);
        // The prefix must be positive, if negative is omitted
        prev = Math.max(prev + nums[i], 0);
    }

    return result;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.