0053. 最大子数组和 #
- 标签:数组、分治算法、动态规划
- 难度:简单
题目大意 #
描述:给定一个整数数组 $nums$。
要求:找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
说明:
- 子数组:指的是数组中的一个连续部分。
- $1 \le nums.length \le 10^5$。
- $-10^4 \le nums[i] \le 10^4$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:动态规划 #
1. 划分阶段 #
按照连续子数组的结束位置进行阶段划分。
2. 定义状态 #
定义状态 $dp[i]$ 为:以第 $i$ 个数结尾的连续子数组的最大和。
3. 状态转移方程 #
状态 $dp[i]$ 为:以第 $i$ 个数结尾的连续子数组的最大和。则我们可以从「第 $i - 1$ 个数结尾的连续子数组的最大和」,以及「第 $i$ 个数的值」来讨论 $dp[i]$。
- 如果 $dp[i - 1] < 0$,则「第 $i - 1$ 个数结尾的连续子数组的最大和」+「第 $i$ 个数的值」<「第 $i$ 个数的值」,即:$dp[i - 1] + nums[i] < nums[i]$。所以,此时 $dp[i]$ 应取「第 $i$ 个数的值」,即 $dp[i] = nums[i]$。
- 如果 $dp[i - 1] \ge 0$,则「第 $i - 1$ 个数结尾的连续子数组的最大和」 +「第 $i$ 个数的值」 >= 第 $i$ 个数的值,即:$dp[i - 1] + nums[i] \ge nums[i]$。所以,此时 $dp[i]$ 应取「第 $i - 1$ 个数结尾的连续子数组的最大和」+「 第 $i$ 个数的值」,即 $dp[i] = dp[i - 1] + nums[i]$。
归纳一下,状态转移方程为:
$dp[i] = \begin{cases} nums[i], & dp[i - 1] < 0 \cr dp[i - 1] + nums[i] & dp[i - 1] \ge 0 \end{cases}$
4. 初始条件 #
- 第 $0$ 个数结尾的连续子数组的最大和为 $nums[0]$,即 $dp[0] = nums[0]$。
5. 最终结果 #
根据状态定义,$dp[i]$ 为:以第 $i$ 个数结尾的连续子数组的最大和。则最终结果应为所有 $dp[i]$ 的最大值,即 $max(dp)$。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$,其中 $n$ 为数组 $nums$ 的元素个数。
- 空间复杂度:$O(n)$。
思路 2:动态规划 + 滚动优化 #
因为 $dp[i]$ 只和 $dp[i - 1]$ 和当前元素 $nums[i]$ 相关,我们也可以使用一个变量 $subMax$ 来表示以第 $i$ 个数结尾的连续子数组的最大和。然后使用 $ansMax$ 来保存全局中最大值。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$,其中 $n$ 为数组 $nums$ 的元素个数。
- 空间复杂度:$O(1)$。
思路 3:分治算法 #
我们将数组 $nums$ 根据中心位置分为左右两个子数组。则具有最大和的连续子数组可能存在以下 $3$ 种情况:
- 具有最大和的连续子数组在左子数组中。
- 具有最大和的连续子数组在右子数组中。
- 具有最大和的连续子数组跨过中心位置,一部分在左子数组中,另一部分在右子树组中。
那么我们要求出具有最大和的连续子数组的最大和,则分别对上面 $3$ 种情况求解即可。具体步骤如下:
- 将数组 $nums$ 根据中心位置递归分为左右两个子数组,直到所有子数组长度为 $1$。
- 长度为 $1$ 的子数组最大和肯定是数组中唯一的数,将其返回即可。
- 求出左子数组的最大和 $leftMax$。
- 求出右子树组的最大和 $rightMax$。
- 求出跨过中心位置,一部分在左子数组中,另一部分在右子树组的子数组最大和 $leftTotal + rightTotal$。
- 求出 $3$、$4$、$5$ 中的最大值,即为当前数组的最大和,将其返回即可。
思路 3:代码 #
|
|
思路 3:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(\log n)$。