链接
题目：
思路：动态规划
模板：
既然是连续子数组，如果我们拿到了当前（0 ~ k-1）的和，对于后面一个（k）即将加入的元素，
如果加上他这一串会变得更大，我们肯定会加上它，如果它自己会比加上前面这一串更大，说明从它自己开始连续子数组的和可能会更大。
dp 数组的定义：以nums[i] 为结尾的「最大子数组和」为 dp[i] ；
按照数学归纳法，假设我们知道了 dp[i-1]，如何推导出 dp[i] ？
dp[i] 有两种「选择」：
①要么与前⾯的相邻子数组连接，形成⼀个和更⼤的子数组；
②要么不与前⾯的子数组 连接，⾃成⼀派，⾃⼰作为⼀个子数组。
class Solution {
public int maxSubArray(int[] nums) {
// dp数组定义： 当前元素为结尾的最大子数组和
int[] dp=new int[nums.length];
Arrays.fill(dp,Integer.MIN_VALUE); // 找大，初始化为小
// base case
dp[0]=nums[0];
for(int i=1;i<nums.length;i++){ // 遍历所有状态
dp[i]=Math.max(nums[i] , dp[i-1]+nums[i]); // 子数组连续 ！
}
int res=Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
res=Math.max(res,dp[i]);
}
return res;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89239.html
