【刷题日记】最大子数组问题

在学习算法时，很多书籍资料都是按照类别进行分类学习的，比如先学分治、动态规划，再学贪心等。本博客的部分文章将根据作者本人的刷题经历，以典型题、模板题、系列题进行总结与发散，站在另一个角度审视这些题目，从而看清问题的本质与事物的全貌。

经典黑书《算法导论》在介绍分治算法时选择了以最大子数组问题为教学案例进行讲解，本文将继续通过这个问题的解决方案进行发散探讨，以串联各种各样的知识。

最大子数组问题：给定数组 A，寻找其中一个 「和最大的子数组」。只有数组中包含负数时，最大子数组问题才有意义。

本文题目难度标识：🟩简单，🟨中等，🟥困难。

题目：🟨53. 最大子数组和 - 力扣（LeetCode）

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

子数组：数组中的一个连续非空序列。

解决方法

传统分治解法

本小节引自《算法导论》第四章内容。本分治策略并不一定是解决这道题的最佳方案。

假定我们要寻找子数组 $A[low..high]$ 的最大子数组，利用分治技术划分为两个规模尽量相等的子数组 $A[low..mid],~A[mid+1..high]$。$A[low..high]$ 的一个最大子数组 $A[i..j]$ 必然是以下三种情况之一：

1. 完全位于子数组 $A[low..mid]$ （左子数组）中，因此 $low\leq i\leq j\leq mid$
2. 完全位于子数组 $A[mid+1..high]$ （右子树组）中，因此 $mid< i\leq j\leq high$
3. 跨越了中点，因此 $low\leq i\leq mid<j\leq high$
   前两种情况实际上仍是最大数组问题，只是规模更小。我们的工作就是寻找跨越中点的最大子数组，然后在三种情况中选取和最大者。

我们可以在线性时间内求出跨越中点的最大子数组：

FIND-MAX-CROSSING-SUBARRAY 花费时间 $\Theta(n)$。

求解最大子数组问题的分治算法的伪代码：

FIND-MAXMUM-SUBARRAY(A,low,high)
	// 基本情况：只有一个元素
	if high==low
		return (low,high,A[low]) 
	else
		mid = (int)(low+high)/2 // 向下取整
		// 左边情况
		(left-low,left-high,left-sum)=FIND-MAXMUM-SUBARRAY(A,low,mid)
		// 右边情况
		(right-low,right-high,right-sum)=FIND-MAXMUM-SUBARRAY(A,mid+1,high)
		// 中间情况
		(cross-low,cross-high,cross-sum)=FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)
		// 比较三种情况的sum值，返回sum最大值所在的三元组
		return (max-low,max-high,max-sum)

运行时间的递归式：

$$T(n) = \begin{cases} \Theta(1) & \text{if}~ n=1 \\ 2T(n /2)+\Theta(n) & \text{if}~ n>1 \end{cases}$$

解为 $T(n)=\Theta(n \lg n)$。

空间复杂度：$O(\log n)$，需要常数个变量用于选取最大值，需要使用的空间取决于递归栈的深度。

动态规划

假设 nums 数组的长度是 n，下标从 0 到 n-1。

我们用 $f(i)$ 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

$$\max_{0\le i \le n-1}\{ f(i) \}$$

因此我们只需要求出每个位置的 $f(i)$，然后返回 f 数组中的最大值即可。动态规划转移方程：

$$f(i)=\max\{f(i-1)+nums[i],nums[i]\}$$

请注意 DP 数组的定义

本题 $f(i)$ 定义为以第 i 个数结尾的「连续子数组的最大和」，就是说计算时必须包括第 i 个数。

传统上，我们可能将 DP 数组定义为：dp[i] 表示“从 0 至 i 处的所有子数组中子数组元素之和的最大值”，然后最后将 dp[n-1] 返回出去就行。但在这个问题中其所求是子数组元素之和的最大值，它相当于对之前的多个元素有依赖关系，如果那样定义的话，则无法建立 dp[i+1] 和 dp[i] 之间的递推关系。

 // 普通的动态规划写法 空间复杂度为 O(n)
 public int maxSubArray(int[] nums) {
	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	int maxAns = nums[0];
	for (int i=1;i<nums.length;i++) {
		dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
		maxAns = Math.max(maxAns,dp[i]);
	}
	// 这里并不是将dp[nums.length-1]直接返回出去，因为这里dp定义的内容并不是题目的答案
	return maxAns; 
}
 
 // Kadane’s Algorithm 空间复杂度为 O(1)。Kadane 算法是基础动态规划的优化。
public int maxSubArray(int[] nums) {
	int pre = 0, maxAns = nums[0];
	for (int x : nums) {
		pre = Math.max(pre + x, x);
		maxAns = Math.max(maxAns, pre);
	}
	return maxAns;
}

复杂度：

• 时间复杂度：$O(n$)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度：$O(1)$。我们只需要常数空间存放若干变量。

相关题目：

• 🟨 152. 乘积最大子数组 - 力扣（LeetCode）
• 🟨 918. 环形子数组的最大和 - 力扣（LeetCode）

根据我的经验，使用动态规划算法时，如果满足以下条件：

• 题目只需要一个最终答案：
  • 它可以是动态规划数组 dp 最后一个元素
  • 或只是单纯需要知道的每一次 dp 计算结果（且只需了解一次）。比如本题。
• 每一次计算 dp[i] 时，只需要了解前面常数的 dp[i-1]、dp[i-2] 等等。

那么就可以考虑压缩 dp 数组的长度，使空间复杂度为 $O(1)$，而不是 $O(n)$。

Kadane’s Algorithm 这名字听起来确实挺高大上的。但是我有一个疑惑——所谓 Kadane’s Algorithm 就是指这种压缩空间的技巧吗？为此我收集了以下资料作为参考。

Kadane’s Algorithm

1. Kadane Algorithm | LeetCode The Hard Way
   The Kadane’s algorithm is a well-known method for solving the problem of finding the maximum sum of a contiguous subarray of a given array of numbers. The basic idea behind the algorithm is to iterate through the array, keeping track of the maximum sum seen so far and the current sum, and updating the maximum sum whenever a new maximum is found. The algorithm has a time complexity of $O(n)$.

2. 动态规划 - 维基百科，自由的百科全书 (wikipedia.org)
   使用动态规划的算法有：最长公共子序列、Floyd-Warshall 算法、Viterbi 算法、Kadane’s algorithm、求解马可夫决策过程下最佳策略、莱文斯坦距离。
   （博主碎碎念：意思就是说 Kadane’s algorithm 是动态规划的一种思想。）

3. 知乎网友 @Vincent Fong
   《论算法领域的俚语》：Kadane 算法、状压 dp、用滚动变量代替一维数组、动态规划之空间复杂度 O(n) 优化到 O(1)…其实说的都是同一个事情。

前缀和

本小节方法灵感来源于 「买卖股票的最佳时机」 这个题目，建议先了解一下题解中「一次遍历」方案。点击链接即可直达本站文章查看问题解法。

如果你已经理解「买卖股票的最佳时机」中一次遍历的算法思路，下面回到本文的「最大子数组问题」的前缀和解决思路：

• 计算数组的前缀和。比如 nums=[5,4,-1,7,8] 得到 arr=[5,9,8,15,23]。
• 原题目的求解变为：找出当 $i<j$ 时，arr[j]-arr[i] 最大的值。
• 和 121. 买卖股票的最佳时机 不同的是，本题需要考虑答案子数组长度不为 0，且长度可能拉满。

public int maxSubArray(int[] nums) {        
	int sum = nums[0];
	int min = nums[0];
	int ans = nums[0];
	for(int i=1;i<nums.length;i++){
		sum+=nums[i];            
		ans=Math.max(Math.max(ans,sum-min),sum);// 比较sum是基于子数组往前拉满的情况
		min=Math.min(min,sum); // 注意：维护历史min在后头
	}
	return ans;
}

连续子数组问题通常可以考虑使用前缀和的方法求解，详看：【刷题日记】学会前后缀分解，就能从「连续子数组」打到「接雨水」。

分治法之线段树

这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作。

对于一个区间 [l,r]，我们取 $m=\lfloor \frac{l+r}{2} \rfloor$，对区间 [l,m] 和 [m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l,m] 区间的信息和 [m+1,r] 区间的信息合并成区间 [l,r] 的信息。

对于一个区间 [l,r]，我们可以维护四个量：

• lSum 表示 [l,r] 内以 l 为左端点的最大子段和
• rSum 表示 [l,r] 内以 r 为右端点的最大子段和
• mSum 表示 [l,r] 内的最大子段和
• iSum 表示 [l,r] 的区间和

以下简称 [l,m] 为 [l,r] 的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」。对于长度为 1 的区间 [i,i]，四个量的值都和 nums[i] 相等。对于长度大于 1 的区间：

• 首先最好维护的是 iSum，区间 [l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
• 对于 [l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
• 对于 [l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
• 当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。我们可以考虑 [l,r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum; // 取 Status 实例的 mSum
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

假设序列 a 的长度为 n。

复杂度：

• 时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为 $O(\log n)$，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是 $O(\sum_{i=1}^{\log n} 2^{i-1}) = O(n)$，故渐进时间复杂度为 $O(n)$。
• 空间复杂度：递归会使用 $O(\log n)$ 的栈空间，故渐进空间复杂度为 $O(\log n)$。

线段树

「线段树方法」相较于「动态规划算法」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？

对于这道题而言，确实是如此的。但是仔细观察「线段树方法」，它不仅可以解决区间 [0,n-1]，还可以用于解决任意的子区间 [l,r] 的问题。如果我们把 [0,n-1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 $O(\log n)$ 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 $O(\log n)$ 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是一种神奇的数据结构——线段树。

本文参考

• 53. 最大子数组和 - 力扣（LeetCode）
• 《算法导论》第四章
• 简介Kadane算法及相关的普通动态规划-CSDN博客
• 经典动态规划问题（理解「无后效性」） - 力扣（LeetCode）