LC53. 最大子数组和（第15题）-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

菜鸟就要从第15题继续

一、题目描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

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

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

贪心算法：首先理解题意，采用贪心算法，遍历数组，依次累加，当小于0时，抛弃之前的数组序列，重新计算，直到最后计算出最大的那一个。

动态规划方法，主要在于对于每新增一个的理解，要判断以最后一个为最大序列的，和新来的一个哪一个大。这样其实判断的是前一个是否大于零，和贪心的逻辑是一样的。

最后是题目提到的分治方法，并不最优，但可以用。要注意代码的写法，尤其是其中四个值得计算

左移运算符，num << 1,相当于num乘以2
右移运算符，num >> 1,相当于num除以2

这道题的重点要思考清楚左端点、右端点，及它们接起来的变化。

三、AC 代码：

1、贪心算法

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
        let count = 0,result=nums[0]
        for (let i = 0; i < nums.length; i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
};
复制代码

2、动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};
复制代码

3、分治算法

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;
};

复制代码