一道很有代表性的数组动态规划问题

连续子数组的最大和

leetcode 剑指 offer 42

问题描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为 $O(n)$。

示例1：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

问题分析

暴力解法

首先考虑暴力解法。也就是先求所有可能的连续子数组，然后找到最大的子数组和。

假设 $nums$ 有 $n$ 个元素，以第 $1$ 个元素开头的子集有 $n - 1$ 种，以第 $2$ 个元素开头的子集有 $n - 2$ 种，以此类推，以第 $n$ 个元素开头的子集有 $1$ 种。

所有连续子集的总数就是：

$$\sum_{i=1}^{n - 1}{i}$$

算法时间复杂度为 $O(n^2)$。

动态规划

在暴力解法中，先选定的是子集合开头的元素，此时还没有遍历到集合末尾，根本无法知道有多少种子集合，也就无法获取子集合中的最大和。

其实可以反过来想，假设选定的是一个子集合的末尾元素，那么此时以当前元素为结尾的子集合有多少种可能就已经确定了，显然就可以获取到最大的子集和。

举几个例子

例如当前遍历到 $nums[1]$，以它为末尾的子集有 $2$ 个：

$$\begin{align*} \begin{array}{|c|c|} \hline -2&1\\ \hline \end{array} \\ \begin{array}{|c|} \hline 1\\ \hline \end{array} \end{align*}$$

例如当前遍历到 $nums[2]$，以它为末尾的子集有 $3$ 个：

$$\begin{align*} \begin{array}{|c|c|c|} \hline -2&1&-3\\ \hline \end{array} \\ \begin{array}{|c|c|} \hline 1&-3\\ \hline \end{array}\\ \begin{array}{|c|} \hline -3\\ \hline \end{array} \end{align*}$$

例如当前遍历到 $nums[3]$，以它为末尾的子集有 $4$ 个：

$$\begin{align*} \begin{array}{|c|c|c|c|} \hline -2&1&-3&4\\ \hline \end{array} \\ \begin{array}{|c|c|c|} \hline 1&-3&4\\ \hline \end{array}\\ \begin{array}{|c|c|} \hline -3&4\\ \hline \end{array}\\ \begin{array}{|c|} \hline 4\\ \hline \end{array} \end{align*}$$

可以看出当遍历到当前位置时，把所有的以前一个元素为结尾的子集再补上一个当前元素；另外再加一个既以当前元素开始，也以当前元素结尾的子集，就得到了以当前元素为结尾的所有可能的子集。

所以，遍历到每个位置时，以次位置元素为结尾的所有可能的子集中最大的和就已经能确认，这样只要遍历一遍 $nums$ 集合，就能够得到答案，时间复杂度为 $O(n)$。

$dp$ 数组定义

$dp[i]$ 代表以 $nums[i]$ 为结尾的所有可能的子集中，最大的子集和。

一般的题目都需要我们单独声明 $dp$ 数组，来存储计算结果，但本题中实际上在参数给入的集合 $nums$ 中直接操作就可以了，只需要额外再维护一个 $max$ 遍历来保存遍历过程中的最大值，也就是结果。

这样节省了空间消耗，空间复杂度 $O(1)$。

初始化方式

对于数组第一个元素，以它结尾的子集显然只有一种可能，就是它本身，所以子集的和的最大值也就是它本身。

也就是：

dp[0] = nums[0]

但是刚刚说过，我们可以使用 $nums$ 集合来作为 $dp$ 数组节省空间，所以实际上也就不需要任何初始化操作。

但是需要把维护的 $max$ 遍历初始化为 $nums[0]$。

max := nums[0]

golang 代码实现

func maxSubArray(nums []int) int {
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        //计算以当前元素为结尾的所有可能的子集中最大的子集和
        //以前一个元素为结尾的最大子集合已经算出，这里只要把当前元素和前一个最大子集和相加，并跟当前元素比较找到最大值即可
        //如果两者相加不大于当前元素，说明以当前元素为结尾的子集中，最大的子集和就是当前元素的值，所以不需要处理
        if nums[i] + nums[i - 1] > nums[i] {
            nums[i] = nums[i] + nums[i - 1]
        }
        //校验是否需要更新最大的子集和
        if nums[i] > max {
            max = nums[i]
        }
    }
    return max
}