53. 最大子序和 【总结|题解四十二】给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
（来源：力扣（LeetCode））
思路：这道题使用动态规划的思路解决并不难。
我们需要求的是一个连续数组，所以当我们分解子问题的时候，不能求的是前k个元素的最大子数组之和，因为这样很可能会跟新元素不连续，就不出最大和。
如示例所示，输入: [-2,1,-3,4,-1,2,1,-5,4]，
f(1) 即[-2]的最大子数组和为 -2
f(2) 即[-2，1]的最大子数组和为 1
f(3) 即[-2，1，-3]的最大子数组和为 1
f(4) 即[-2，1，-3，4]的最大子数组和为 4
f(5) 即[-2，1，-3，4，-1]的最大子数组和为 [ 4，-1] = 2
我们可以看到，f(3)的最大子数组和为1，位于数组的中部，当f(4)加入新元素时，我们想知道f(3)的最大数组和能否和新元素求出最优解时，却发现它们并不连续。
因此，我们分析子问题的时候只需要考虑数组尾部的子数组，这样加入新元素时就是连续的。重新计算f(3)、f(4)的最大和：
f(3) 即[-2，1，-3]的最大子数组和为 [1, -3] = -2
f(4) 即[-2，1，-3，4]的最大子数组和为 4
我们可以写出递推关系，计算[0…k]的子数组最大和时，要么是把新元素nums[k - 1]加入到前一个子问题的最大和中，要么新元素nums[k -1]就是最大和。
递推公式为 f(k) = max{f(k -1) + nums[k -1], nums[k -1]},
简化可得，f(k) = max{f(k -1), 0} + nums[k - 1].
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[0] = 0;
int res = Integer.MIN_VALUE;
for (int i = 1;
i <= n;
i++) {
dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1];
res = Math.max(res, dp[i]);
}return res;
}
}
推荐阅读
- 笔记|如何在Windows11安装安卓子系统（）
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 2021年下半年《信息系统项目管理师》真题
- 个人理解|【C语言基础之类型转换】
- 学习分享|【C语言函数基础】
- 个人理解|【C语言实现井字棋及电脑落子优化】
- 总结|python爬虫入门
- Python|蓝桥杯 平面切割 Python
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 笔记|这是一个关于face_recognition和dlib库的安装（亲测有用，毕竟我代码都写出来了）