53. 最大子序和

小目标：百篇题解之五，破百开源成库。关注我（Github、力扣），即可获取最新题解。

题目描述

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

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

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

相关信息：

难度：简单
标签：数组、分治、动态规划

题解

这道题目的真实难度应该是不止简单这个层级，我在读完题目之后的第一个想法就是使用暴力的滑动窗口，但是一看这个范围，估摸着必然会超时，于是就放弃这个想法。在看完所有题解以后，总结了一下目前的解法，分别是暴力枚举、动态规划以及分治算法三种大的方向，其中还有很多比较小的一些解法基本都是基于这三种方法去进一步改进，或者说是具体实现的代码稍有不同。

求子序列的最大和，一般都少不了遍历，所以我们可以先思考一下，数组或者字符串的子序列有几种遍历方式？

在《详细解读动态规划的实现, 易理解》一文中总结的三种遍历方式：

以某个节点开头的所有子序列：如：[a]、[a,b]等以 a 开头的子序列，这种方式常用于暴力解法。
根据子序列的长度为基础：如先遍历出子序列长度为 1 的子序列，再遍历出长度为2的等等。
以某个节点结尾的所有子序列：如：[b]、[a,b]等以 b 结尾的子序列，这种方式可以产生递推关系，常用于动态规划中。

下面就从暴力枚举开始一步步优化代码：

方法一：暴力枚举

暴力出不了奇迹(超出时间限制🚫)

我们可以采用上文中提到的第一种遍历方式，使用首尾指针，分别指向子序列的首尾，再依次移动他们达到循环所有子序列的目的，同时再使用一个for循环计算首尾指针之间元素的和。故此需要三个for循环，故时间复杂度达到了O(n3)级别，必然会超出时间限制。

var maxSubArray = function (nums) {
    //暴力循环
    let max = -Infinity;
    for (let start = 0; start < nums.length; start++) {
        for (let end = start; end < nums.length; end++) {
            let sum = 0;
            for (let i = start; i <= end; i++) {
                sum += nums[i]
            }
            max = max > sum ? max : sum;
        }
    }
    return max
};

前缀和+暴力

上边这段代码每次在计算和的时候都是从子序列从头到尾进行计算，尽管前一个子序列与后一个子序列只有最后一个元素不同，也会再次把前面的相同元素重新计算一次，但是这样就产生了很多重复计算，我们可以将sum变量提到外层去，让它一直保持子序列前面的和，这样就能大大降低重复计算，使得时间复杂度可以将至O(n2)。而这便是所谓的前缀和：

/**
执行用时：248 ms   >5.49%
内存消耗：39.4 MB  >41.22%
*/
var maxSubArray = function (nums) {
    //前缀和+暴力循环
    let max = -Infinity;
    let sum;
    for (let start = 0; start < nums.length; start++) {
        sum = 0;//重置为0
        for (let end = start; end < nums.length; end++) {
            sum += nums[end]
            max = max > sum ? max : sum;
        }
    }
    return max
};

优化前缀和+一次循环

上边，我们使用了前缀和优化了纯暴力，但是我们细心地思考前缀和的计算过程，那你肯定会惊奇地发现，其实计算前缀和的过程中也有非常多的重复计算，比如外部循环的第一轮循环的子序列和第二轮循环的子序列，它们只是头部和尾部有所不同，中间的元素也是完全相同的，但还是会重新计算一次。那我们可以想办法优化这一部分的重复计算，使得时间复杂度降为O(n)。那我们可以改变和的计算方式，我们可以定义一个函数 S(i) ;它可以计算数组从 0 到 i（包括 0 和 i ）位置的元素和，那么从 i 到 j （ j > i ）的和就等于 S( j ) - S(i)。

进一步分析，因为我们要求的是子序列的最大和，那么在一次循环的过程中，我们只需要将当前位置的 S(i) 减去前面 i-1个位置中的最小值，就能得到以当前位置结尾的所有子序列和的最大值。所以我们并不需要维持所有位置的 S()，只需要一个 min 变量来记录所有位置中的 S() 的最小值就可以了。

/*
执行用时: 80 ms
内存消耗: 39.1 MB
*/
var maxSubArray = function (nums) {
    //优化前缀和+一次循环
    let max = nums[0];
    let sum = 0;
    let min = 0;
    for (let start = 0; start < nums.length; start++) {
        sum += nums[end]
        max = max > (sum - min) ? max : (sum - min);
        min = sum < min ? sum : min;
    }
    return max
};

方法二：动态规划

许多题解都说动态规划的难点在于找到状态转移方程，但是我对于这还没有入门动态规划的人来说，找到状态都是一件难事儿🌚 。

在本题中的最佳子结构便是以每个位置为终点的最大子数列都是基于前一位置的最大子数列计算得出的。故其状态转移转移方程为：sum[i] = max(sum[i-1]+a[i],a[i])；这样说起来还是有些抽象，不过我也无法做到更好的解释了，可以结合下面的详细代码理解。

// Kadane算法扫描一次整个数列的所有数值，
// 在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。
// 该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。
// 因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出, 
// 该算法可看成动态规划的一个例子。
// 状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}   
// 其中(sum[i]记录以a[i]为子序列末端的最大序子列连续和)
function  maxSubArray2  ( nums ) {
    if (!nums.length) {
        return;
    };
    // 在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。
    let max_ending_here = nums[0];
    let max_so_far = nums[0];

    for (let i = 1; i < nums.length; i ++ ) {
        // 以每个位置为终点的最大子数列 都是基于其前一位置的最大子数列计算得出,

        max_ending_here = Math.max ( nums[i], max_ending_here + nums[i]);
        max_so_far = Math.max ( max_so_far, max_ending_here);
    };

    return max_so_far;
};

上面这段代码来自在《详细解读动态规划的实现, 易理解》，不知道你在阅读完这一部分代码之后，有没有感觉这部分代码的逻辑和前面的优化前缀版本的代码逻辑非常相似，都是在保存以该点数值为结束的子序列的最大和，只是实现方式不同。

在充分理解了上面的代码之后，我也通过一些 reduce() 方法将上边的代码写成了一行的模式，逻辑上是完全一样的，你可以尝试理解一下，但是我非常不推荐你写这样毫无可读性的代码。我写这样一行代码，主要是想尝试能否在每一道题中都写出一行代码的解决方案，仅个人喜好，不喜勿喷，感谢！

var maxSubArray = function(nums) {
    return nums.reduce((pre,val)=>{let tempPre=Math.max(pre[0]+val,val);return[tempPre,Math.max(pre[1],tempPre)]},[0,nums[0]])[1]
};

方案三：分治法

分治算法的基本思想是：先将问题分解为子问题；解决子问题后，再将子问题合并，解决主问题。

在本题中应用分治算法的基本思路是：

将数组从中间分为两个部分。例如 [1,2,3,4]分为 [1,2] 和 [3,4]
通过递归计算，得到左右两部分的最大子序列和是lsum，rsum。
从数组中间开始向两边计算最大子序列和 cross
返回 max(lsum,corss,rsum)

可能你会疑惑为什么会有第 3 步？因为分治法的关键是，最大子序列和只有可能出现在左子数组、右子数组或者是横跨左右子数组三种情况。前面第 2 步解决了出现在左/右子数组中的情况，而第3步解决了横跨左右子数组的情况。

详细过程可以参考下图（来自官方图解）：

// ac地址：https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址：https://xxoo521.com/2020-03-09-max-sub-sum/

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number} mid
 * @return {number}
 */
function crossSum(nums, left, right, mid) {
    if (left === right) {
        return nums[left];
    }

    let leftMaxSum = Number.MIN_SAFE_INTEGER;
    let leftSum = 0;
    for (let i = mid; i >= left; --i) {
        leftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, leftSum);
    }

    let rightMaxSum = Number.MIN_SAFE_INTEGER;
    let rightSum = 0;
    for (let i = mid + 1; i <= right; ++i) {
        rightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, rightSum);
    }

    return leftMaxSum + rightMaxSum;
}

/**
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
function __maxSubArray(nums, left, right) {
    if (left === right) {
        return nums[left];
    }

    const mid = Math.floor((left + right) / 2);
    const lsum = __maxSubArray(nums, left, mid);
    const rsum = __maxSubArray(nums, mid + 1, right);
    const cross = crossSum(nums, left, right, mid);

    return Math.max(lsum, rsum, cross);
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    return __maxSubArray(nums, 0, nums.length - 1);
};

以上就是本题的所有题解啦，感谢你能看到这里，如果本文对你有所帮助的话，别忘了给一个 Star 嗷～
如果你对题解中的代码有不一样的优化意见，也欢迎你在 issue 中指出～
最重要的是不要忘了点点关注嗷（Github、力扣），以便获取我最新的题解以及文章通知。

参考

本文部分内容参考了以上文章，感谢原作者的创作～

【53. 最大子序和】题解