【剑指 Offer 】42. 连续子数组的最大和

题目：42. 连续子数组的最大和

分析：

状态dp[i]: 表示从0到i的连续子数组的最大和；初始状态：dp[0] = nums[0];转移方程: dp[i] = Math.max(dp[i-1],0) + nums[i];

最后求出的dp[]数组相当于一个状态表，每个位置代表着以这个位置结尾的最大连续子数组的最大和。 所以，整个数组nums中连续子数组的最大和，就是dp[]数组中最大的值。

解题思路：

创建一个dp[]数组,一个记录最大和的变量res;赋初始值dp[0];遍历数组，更新dp[i],更新最大和res;返回res;

代码：

class Solution { public int maxSubArray(int[] nums) { int len = nums.length; int[] dp = new int[len]; dp[0] = nums[0]; int res = nums[0]; for(int i = 0; i < len; i++){ dp[i] = Math.max(dp[i],0) + nums[i]; res = Math.max(res,dp[i]); } return res; } }