Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

Given an array of integers, nums, find a contiguous subarray with the largest sum (the subarray contains at least one element) and return its largest sum.

 

Example 1: input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 description: the maximum sum of consecutive subarrays [4,-1,2,1] is 6. Example 2: Input: nums = [1] Output: 1 Example 3: Input: nums = [0] Output: 0 Example 4: Input: nums = [-1] Output: -1 Example 5: Input: nums = [-100000] Output: -100000Copy the code

Ii. Thinking analysis:

  • Traversal, comparing the maximum value of the elements in each traversal
  • It’s kind of like the idea of “scrolling arrays.”

Three, AC code

/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let res = nums[0]; let sum = 0; for (let num=0 ; num<nums.length; num++) { if (sum > 0) sum += nums[num]; else sum = nums[num]; res = Math.max(res, sum); } return res; }; Time: 96 ms Memory: 39.2 MBCopy the code

Four,

  • Of course, there is more than one method, the official partition, see more trouble, a simple understanding;
function Status(l, r, m, i) {
    this.lSum = l;
    this.rSum = r;
    this.mSum = m;
    this.iSum = i;
}

const pushUp = (l, r) => {
    const iSum = l.iSum + r.iSum;
    const lSum = Math.max(l.lSum, l.iSum + r.lSum);
    const rSum = Math.max(r.rSum, r.iSum + l.rSum);
    const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
    return new Status(lSum, rSum, mSum, iSum);
}

const getInfo = (a, l, r) => {
    if (l === r) {
        return new Status(a[l], a[l], a[l], a[l]);
    }
    const m = (l + r) >> 1;
    const lSub = getInfo(a, l, m);
    const rSub = getInfo(a, m + 1, r);
    return pushUp(lSub, rSub);
}

var maxSubArray = function(nums) {
    return getInfo(nums, 0, nums.length - 1).mSum;
};

Copy the code

For reference only

Refer to the topic

  • Force button (LeetCode)