# NC19.连续子数组的最大和

# 描述

输入一个长度为n的整数数组a,数组中的一个或者多个整数数组组成一个子数组，求所有子数组的和的最大值，要求时间复杂度为O(n).

# 示例

输入: [1,-2,3,10,-4,7,2,-5]
返回值: 18
说明：和最大的子数组为 {3,10,-4,7,2} 因此输出为该子数组的和18。

1
2
3

# 题解：

连续子数组问题是典型的动态规划问题, 我们首先进行状态定义：

dp[i] 表示以nums[i]为结尾的连续子数组的最大和(这道题目属于基础的动态规划，题目问什么就按什么做状态定义)

在这样的条件下，nums[i]必须被选取, 因为已经明确说明结尾，结尾必须包含。既然它被选取，那么它前面的子数组的和是不是正数就需要分类讨论。

状态转移方程:

如果 dp[i-1] > 0, dp[i] = dp[i-1] + nums[i]
如果 dp[i-1] <= 0, dp[i] = nums[i]

总结一下，就是dp[i-1] 如果大于零肯定对 dp[i] 有增益效果，如果dp[i-1]小于等于0 肯定没有帮助，此时dp[i] 就是 nums[i]

初始化的状态：dp[0] = nums[0]

和最大的连续子数组可能以任意一个数字结尾，因此我们需要输出状态数组的最大值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var FindGreatestSumOfSubArray = function (array) {
  // 将输入数组的长度保存下来 
  let len = array.length;
  // 如果数组中一个元素也没有 最大和就是0
  if (len === 0) {
    return 0
  }
  // dp[i]: 以nums[i] 即结尾的和最大连续子数组的和
  // dp 数组的长度
  let dp = new Array(len);
  dp[0] = array[0]

  let max = array[0];
  for (let i = 1; i < len; i++) {
    // 这里不需要进行分类讨论 使用 Math.max 直接判断了
    dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
    max = Math.max(dp[i], max);
  }
  return max
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析：

时间复杂度: O(N),只遍历一遍数组
空间复杂度: O(N),状态数组的长度为N