动归训练二：Leetcode 53. 最大子序和
问题描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
原题链接：53. 最大子序和
题解
按照我们说的动态规划三部曲来，没看过的看我之前写的文章：告别动态规划，谈谈我的一些经验
一、定义数组的含义
本题是求找到一个具有最大和的连续子数组，并且子数组必须至少含有一个元素，那么 dp[i] 的含义应该定位为啥呢？
这个其实不是那么好找，需要大家多做一做题，才可以很快着准确判断出来，对于这道题， dp[i] 的含义是以 nums[i] 结尾的子序的最大和。那么我们要找的答案就是
max = max(dp[0], dp[1],….., dp[n-1])。就是看看以哪个 num[i] 结尾的连续子序列和是最大的。
二、找出数组元素之间的关系式
对于每一个 dp[i]，我们必须以 nums[i] 结尾，那么对于 dp[i] 与 dp[i-1] 的关系则为
dp[i] = max(dp[i-1] + nums[i], nums[i])
其实这很好理解，假如 dp[i] 是个正数，那我 dp[i] 肯定要你，把你包含进来，假如 dpj[i-1] 是个负数，那么不好意思，你就是个累赘，我 dp[i] 不需要你。
三、找出数组初始值
初始值还是比较容易找的，当只有一个元素的时候
dp[0] = num[0]
所以最终代码如下
public class lc53_MaximumSubarray {
public int maxSubArray(int[] nums) {
int len = nums.length;
if(len == 0)
return 0;
int [] dp = new int[len];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i<len;i++){
dp[i] = (dp[i-1]+nums[i] > nums[i]) ? dp[i-1]+nums[i] : nums[i];
if (dp[i]>max)
max = dp[i];
}
return max;
}
}
评论(5)
帅地，这节搞混了
已经更改，我脑子也真是有问题，，题解都能混淆
这一节的 找出数组元素直接的关系式 部分，你搞混了
太赛了！！请加紧更新
加速更新～