labuladong 动态规划套路:最大子数组和
NOTE:
一、原题: leetcode 53. 最大子序和 简单
思路分析
解决这个问题需要动态规划技巧,但是dp
数组的定义比较特殊。按照我们常规的动态规划思路,一般是这样定义dp
数组:
nums[0..i]
中的「最大的子数组和」为dp[i]
。
NOTE:
非单调的,因此无法使用上述definition
如果这样定义的话,整个nums
数组的「最大子数组和」就是dp[n-1]
。如何找状态转移方程呢?按照数学归纳法,假设我们知道了dp[i-1]
,如何推导出dp[i]
呢?
如下图,按照我们刚才对dp
数组的定义,dp[i] = 5
,也就是等于nums[0..i]
中的最大子数组和:
那么在上图这种情况中,利用数学归纳法,你能用dp[i]
推出dp[i+1]
吗?
实际上是不行的,因为子数组一定是连续的,按照我们当前dp
数组定义,并不能保证nums[0..i]
中的最大子数组与nums[i+1]
是相邻的,也就没办法从dp[i]
推导出dp[i+1]
。
所以说我们这样定义dp
数组是不正确的,无法得到合适的状态转移方程。对于这类子数组问题,我们就要重新定义dp
数组的含义:
以nums[i]
为结尾的「最大子数组和」为dp[i]
。
这种定义之下,想得到整个nums
数组的「最大子数组和」,不能直接返回dp[n-1]
,而需要遍历整个dp
数组:
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
依然使用数学归纳法来找状态转移关系:假设我们已经算出了dp[i-1]
,如何推导出dp[i]
呢?
可以做到,dp[i]
有两种「选择」,要么与前面的相邻子数组连接,形成一个和更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。
如何选择?既然要求「最大子数组和」,当然选择结果更大的那个啦:
// 要么自成一派,要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
综上,我们已经写出了状态转移方程,就可以直接写出解法了:
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
以上解法时间复杂度是 O(N),空间复杂度也是 O(N),较暴力解法已经很优秀了,不过**注意到dp[i]
仅仅和dp[i-1]
的状态有关**,那么我们可以进行「状态压缩」,将空间复杂度降低:
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
// dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}
最后总结
虽然说动态规划推状态转移方程确实比较玄学,但大部分还是有些规律可循的。
今天这道「最大子数组和」就和「最长递增子序列」非常类似,dp
数组的定义是「以nums[i]
为结尾的最大子数组和/最长递增子序列为dp[i]
」。因为只有这样定义才能将dp[i+1]
和dp[i]
建立起联系,利用数学归纳法写出状态转移方程。