题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分
示例
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示
1 <= nums.length <= 105
-104 <= nums[i] <= 104
思路
-
如果数组都是正数的话，全部加起来就好了，题目中给出的**num[i]**可能为负数，就会涉及到比如在区间[i,j]之间上的最大和为sum1的话，加上下一个元素 num[j+1]，是否可能是小于sum1的，如果小于的话，就舍弃，另外如果sum1本来就是负数的话，就可以直接把原来的sum1给丢弃了，取最近的num[j+1]就ok了
-
定义int[] dp，当下标来到i的位置的时候，当前的最大和是dp[i]
-
递推公式文章来源：https://www.toymoban.com/news/detail-681678.html
-
dp[i] = max(dp[i-1] + num[i], num[i]); -
完整代码（每次都更新结果）文章来源地址https://www.toymoban.com/news/detail-681678.html
-
public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; //当i=0的时候，dp[0]自然就等于num[0]了，就一个元素 dp[0] = nums[0]; int res = dp[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); //每次计算完dp[i]后都取最大值（题目要求返回这个最大值） res = Math.max(dp[i], res); } return res; }
到了这里，关于53. 最大子数组和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
