本文共 668 字，大约阅读时间需要 2 分钟。

题目描述如下：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题目思路如下：

要求出使sum最大的连续子串，可知当当前sum<0时，下一次计算之后的求和值肯定小于下一个值，推出关系式为dp[i] = Math.max(sum,0) + nums[i];

因为将dp初始化为int[nums.length+1],所以实际的递推关系式为dp[i]=Math.max(sum,0) + nums[i-1];

代码如下：

public class Solution {

   public int maxSubArray(int[] nums) { int len = nums.length; int[] dp = new int[len + 1]; int max = Integer.MIN_VALUE; for(int i = 1; i <= len; i++){ dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1]; if(dp[i] > max) max = dp[i]; } return max; } }

转载地址：http://eobvb.baihongyu.com/