[每日一题] 第十五题：连续子数组的最大和
0 / 0 / 创建于 4年前
DRose 的个人博客
题目描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100
题解
方法一：动态规划
解题思路：
| 常见解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力搜索 | O(N^2) | O(1) |
| 分治思想 | O(NlogN) | O(logN) |
| 动态规划 | O(N) | O(1) |
动态规划是本题的最优解法，以下按照标准流程解题。
动态规划解析：
状态定义： 设动态规划列表 dp，dp[i] 代表以元素 nums[i] 为结尾的连续子树组最大和。
- 为何定义最大和 dp[i] 中必须包含元素 nums[i]：保证 dp[i] 递推到 dp[i+1] 的正确性：如果不包含 nums[i]，递推时则不满足题目的 连续子数组 的要求。
转移方程： 若 dp[i-1]<=0，说明 dp[i-1] 对 dp[i] 产生负贡献，即 dp[i+1] + nums[i] 还不如 nums[i] 本身大。
- 当 dp[i-1] > 0 时：执行 dp[i] = dp[i-1] + nums[i]；
- 当 dp[i-1] <= 0 时：执行 dp[i] = nums[i]；
初始状态： dp[0]=nums[0]，即以 nums[0] 结尾的连续子数组的最大和为 nums[0]。
返回值： 返回 dp 列表中的最大值，代表全局最大值。
![[每日一题] 第十五题：连续子数组的最大和](https://cdn.learnku.com/uploads/images/202007/31/61979/eCRzTNvylf.png!large)
空间复杂度降低：
- 由于 dp[i] 只与 dp[i-1] 和 nums[i] 有关系，因此可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。
- 由于省去 dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1)。
复杂度分析
- 时间复杂度： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
- 空间复杂度： 使用常数大小的额外空间。
代码
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
个人理解
- 确定动态规划解题思路： 没有经验的话把这道题想成用动态规划去解决还是很难的，这题能用动态规划去实现，有一个很重要的一点，确定状态，想到用 dp[i] 来表示到 nums[i] 的最大值这个很重要。
- 状态转移方程： 因为我们要进行空间优化，所以我们省去了 dp 数组，而是将原来的 nums 数组当成 dp 数组，所以我们应该想到状态转移方程为
nums[i] += (nums[i-1] > 0) ? nums[i-1] : 0;。 - 大小比较： 这个我是第一次使用，
Math.max()方法，里面要传入两个值，所以每次 for 循环都要比较。
题解来源
作者：jyd
链接：leetcode-cn.com/problems/lian-xu-z...
来源：力扣（LeetCode）
来源
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/lian-xu-z...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号