# [动态规划] 最大子序和

[动态规划] 最大子序和

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

TIP

示例:

输入: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

输出: 6

解释: 连续子数组 [4, -1, 2, 1] 的和最大，为 6

# 思路

找到子序列的结束节点，从后往前推算最大和。

# 状态数组

dp[i]表示：以下标 i 为子序列末端的最大子序列和。

因为这样可以方便 运用递归形式 解决问题（见具体思路）。

# 状态转移方程

dp[0] = nums[0] // 因为子序列的最小长度为1
dp[i] = max{ dp[i - 1] + nums[i], nums[i] }

1
2

# 具体思路

示例：[a, b, c, d, e]

通常遍历子串或者子序列有三种遍历方式：

以某个节点为开头的所有子序列
- （如以a开头：[a]、[a, b]、[a, b, c]；以b开头：[b]、[b, c]）；
根据子序列的长度为标杆
- （如：先遍历出子序列长度为1的子序列；再遍历出长度为2的）
以子序列的结束节点为基准，先遍历出“以某个节点为结束的所有子序列”。因为每个节点都可能会是子序列的结束节点。因此要遍历下整个序列
- （如：以b为结束点的所有子序列[a, b]、[b]；以c为结束点的所有子序列[a, b, c]、[b, c]、c）

TIP

第一种遍历方式通常用于暴力解法

第二种方式比较少见

第三种方式因为可以产生递推关系。所以采用动态规划时，经常采用这种遍历方式（如背包问题，最大公共子串）。

所以可以说，这道题的解法为 动态规划 + 以子序列的结束点为基准。

# 代码实现

function maxSubArray (nums) {
    if (!nums.length) return;

    let sum = nums[0]; // sum表示：以“当前位置的数值”为结束点时的最大子序列和
    let ans = nums[0]; // ans表示：整个数组中，最大的子序和

    for (let i = 1; i < nums.length; i++) {
        sum = Math.max(sum + nums[i], nums[i]) // 每个“sum”都是基于它前一位置的“sum”（即最大子序列和）计算出
        ans = Math.max(sum, ans)
    }

    return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 参考链接

leetcode-最大子序和 (opens new window)