[路飞]_leetcode-53-最大子数组和

「这是我参与2022首次更文挑战的第6天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

首先说明本题不会讲解 分治法 解题，是因为要用到一种高级数据结构字段树，而且本题我们的题解是达到了最优解的（时间复杂度 O(n)，空间复杂度 O(1)）。

通常需要求解区间和的问题，大概率都需要借助前缀和数组解题。这里照顾不了解 前缀和数组 的小伙伴，我们来讲一下 前缀和数组。

前缀和数组

所谓前缀和数组，就是数组中的每一项，等于原数组中当前位置及之前元素的和值。

例如原数组为 [1,2,3,4], 前缀和数组为 [0,1,3,6,10]。 要注意的是前缀和数组中默认第一位是 0,所以前缀和数组的长度会比原数组长度 +1。

为什么要有一个前置 0呢？

1. 方便计算前缀和数组的第一项的值。因为我们求前缀和数组中当前项值的时候，只需要将前一项的值加上原数组前位置的元素值即可，那么为了原数组第一个元素计算的时候有前一项值，所以需要一个前置 0。
2. 方便计算区间和值。观察前缀和数组可以发现，后面的值减去前面的值，刚好等于原数组中该区间中的元素和值，即区间和值。那每一项减去最前面的 0,其实就是从原数组下标 0到当前位置的区间和值（这里要注意的是，因为有一个前置 0，所以前缀和数组中的下标等于原数组中的下标 +1）。

我们利用前缀和数组，可以很方便的求得某一段区间中元素的和值，也就是本题中的子数组和值。

所以我们可以遍历前缀和数组，同时记录前面区间中的最小值，然后用当前值减去前面区间的最小值，这样就得到了以当前位置为结尾，所能得到的最大的子数组和值。

然后尝试用这个结果更新结果值，最后就得到了数组中的最大子数组和。

要注意的是，在这个过程中，还需要尝试用当前位置的前缀和结果更新最小值，保证最小值保存的是已处理区间的最小值。

动画演示

代码实现

var maxSubArray = function(nums) {
  // 初始化之前区间的前缀和最小值为前置0
  let min = 0,
  // 第 0 前缀和结果为 前置0
  sum = 0,
  // 最大子数组和为负无穷
  max = -Infinity;
  // 遍历输入数组
  for(let i = 0;i<nums.length;i++){
    // 获取当前位置前缀和
    sum += nums[i]
    // 用当前位置前缀和减去前面区间前缀和的最小值
    // 就得到了以当前位置为结尾所能得到的最大子数组和
    // 用这个结果尝试更新结果值
    max = Math.max(max,sum-min)
    // 用当前位置前缀和尝试更新最小值
    min = Math.min(min,sum)
  }
  return max;
};
复制代码

至此我们就完成了 leetcode-53-最大子数组和

如有任何问题或建议，欢迎留言讨论！