最大子序和

题目

题目来源：力扣（LeetCode）

给定一个整数数组 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

思路分析

动态规划

• 状态定义

dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和

• 状态转移方程

dp[i] 只有两个方向可以推导出来：

• dp[i - 1] + nums[i]：如果 dp[i - 1] > 0，那么可以把 nums[i] 直接接在 dp[i - 1] 表示的那个数组的后面，得到和更大的连续子数组；

• nums[i]：如果 dp[i - 1] <= 0，那么 nums[i] 加上前面的数 dp[i - 1] 以后值不会变大。于是 dp[i] 「另起炉灶」，此时单独的一个 nums[i] 的值，就是 dp[i]。

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

• 状态初始化

从状态转移方程可以看出来 dp[i] 是依赖于 dp[i - 1] 的状态，dp[0] 就是递推的基础。

dp[0] 根据定义，只有 1 个数，一定以 nums[0] 结尾，因此 dp[0] = nums[0]。

• 确定遍历顺序

状态转移方程中 dp[i] 依赖于dp[i - 1] 的状态，因此需要从前向后遍历。

• 空间优化

根据 状态转移方程 ，dp[i] 的值只和 dp[i - 1] 有关，因此可以使用「滚动变量」的方式将代码进行优化。因此我们可以只用一个变量 pre 来维护对于当前 dp[i] 的 dp[i - 1] 的值是多少，从而让空间复杂度降低到 O(1)

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  // pre 用来维护对于当前 dp[i] 的 dp[i - 1] 的值是多少
  let pre = 0, ans = nums[0];
  for (const num of nums) {
    pre = Math.max(pre + num, num);
    ans = Math.max(ans, pre);
  }
  return ans;
};