LeetCode53 最大子序和

• 题目
• 解题
• • 解题一：动态规划
  • 解题二：分治法

题目

解题

解题一：动态规划

// javascript
var maxSubArray = function(nums) {
    let numLen = nums.length;
    let curSum = nums[0], maxSum = nums[0];
    for (let i = 1; i < numLen; i++) {
        curSum = Math.max(nums[i], curSum + nums[i]);
        maxSum = Math.max(maxSum, curSum);
    }
    return maxSum;
};

解题二：分治法

// javascript
var Status = function(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(l.mSum, r.mSum, l.rSum + r.lSum);
    return new Status(lSum, rSum, mSum, iSum);
};

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

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

解法二存在的意义：