简单

问题描述

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

动态规划

设 $dp[i]$ 为以 $i$ 结尾的最大连续子数组和，对于 $nums[i]$ 是否需要成为一个单独的子数组，取决于 $nums[i]$ 是否小于 $0$。 如果 $nums[i]$ 大于 $0$，那么 $dp[i-1] + nums[i]$ 必然大于 $dp[i-1]$，$nums[i]$ 可以添加到 $dp[i-1]$的数组中，成为和更大的数组，若 $nums[i]$ 小于 $0$ ，那么以 $i$ 结尾的最大连续子数组必然只能是 $nums[i]$ 一个数组成的数组。因此有状态转移方程：

$$dp[i] = max(dp[i-1]+nums[i], nums[i])$$

其中必然存在最大和的连续子数组，返回最大和的连续子数组的和即可。

由于 $dp[i]$ 只于 $dp[i-1]$ 相关，因此可以使用一个变量对状态进行压缩。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = nums[0]
  let dp = nums[0]
  for (let i = 1; i < nums.length; i++) {
    dp = Math.max(dp + nums[i], nums[i])
    max = Math.max(max, dp)
  }
  return max
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$