题目链接：力扣53-最大子序和
前情提要：
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。
题目思路:
本题的题目描述很清晰，就是想让我们找到本数组的具有最大和的连续子数组。
直接用我们的dp五部曲来系统分析一下。
1.确定dp数组和i下标的含义。
dp[i] 指的就是以i为结尾的最大连续子数组和。
注意这里是以i为结尾，所以i必须是该最大连续子数组的最后一个元素，所以本题收集结果的地方可能是任意位置。
即所有以下标i的元素结尾的最大连续数组和都可能是我们的结果。
2.确定递推公式。
既然我们考虑下标为i的元素是连续子数组和的一部分，那我们就要遍历数组中的每一个元素。
因为我们是要找最大和的连续子数组。
所以遍历到i时，有俩种情况。
-
第一种 选择该元素作为子数组和的最后一个元素
如果是第一种的话，那么选择了该元素，我们肯定就要把这个元素加入到我们的连续子数组中，加到哪个连续子数组中呢？
就是加到dp[i - 1]中，就是以i前一个元素为结尾的连续子数组中。
所以代码就为：dp[i] = dp[i - 1] + nums[i];
-
第二种 另起炉灶，以该元素作为连续子数组的起点，把前面的连续数组的和都不要。
所以代码就为 dp[i] = nums[i];
因为我们要取最大值，所以要对俩种情况取一个最大值。
dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
3.dp初始化。
本题可以从递推公式可以看出dp[i]的状态依靠于dp[i - 1]，所以所有状态的起点就是dp[0]。
dp[0]指的就是以下标0为结尾的最大连续子数组和。
dp[0]只有一个下标为0的元素，所以他的连续子数组和就为nums[0]；
所以初始化dp[0] = nums[0]；
4.确定dp的遍历顺序。
由递推公式也可以看出dp[i]的状态依靠于dp[i - 1]，所以一定是从前往后遍历的。
5.如果没有ac打印dp数组 利于debug。
在前面说到 最大结果的地方可以是任何地方，所以我们怎么收集结果呢？
遍历一遍求最大值即可。
最终代码：
class Solution {public int maxSubArray(int[] nums) {//dp数组的定义if(nums.length == 1)return nums[0];int [] dp = new int [nums.length + 1];//因为dp数组的定义是以下标i结尾的最大子数组和，所以结果可能在任何地方。//所以还需要我们遍历一遍dp数组来求出最大的结果 这里使用了一个代码技巧 直接在循环里面 边更新边比较//这里的i是从1开始//为了比较所有的dp数组 所以我们的result就初始化为nums[0] 这样就能dp[0] = nums[0];int result = dp[0];//为什么这里是从1开始，因为下标0我们已经初始化了for(int i = 1;i < nums.length;i ++){dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);//边推出dp数组边比较收集结果result = Math.max(dp[i],result);}return result;}
}
这一篇博客就到这了，如果你有什么疑问和想法可以打在评论区，或者私信我。
我很乐意为你解答。那么我们下篇再见！