给一个数组，找出一个连续的子数组，长度任意，和最大。

解法一 动态规划思路一

用一个二维数组 dp[ i ] [ len ] 表示从下标 i 开始，长度为 len 的子数组的元素和。

这样长度是 len + 1 的子数组就可以通过长度是 len 的子数组去求，也就是下边的递推式，

dp [ i ] [ len + 1 ] = dp[ i ] [ len ] + nums [ i + len - 1 ]。

当然，和第 5 题一样，考虑到求 i + 1 的情况的时候，我们只需要 i 时候的情况，所有我们其实没必要用一个二维数组，直接用一维数组就可以了。

publicintmaxSubArray(int[] nums) {
intn=nums.length;
int[] dp=newint[n];
intmax=Integer.MIN_VALUE;
for (intlen=1; len<=n; len++) {
for (inti=0; i<=n-len; i++) {
//直接覆盖掉前边对应的情况就行dp[i] =dp[i] +nums[i+len-1];
//更新 maxif (dp[i] >max) {
max=dp[i];
            }
        }
    }
returnmax;
}

时间复杂度：O（n²）。

空间复杂度：O（n）。

解法二 动态规划思路二

参考这里。

用一个一维数组 dp [ i ] 表示以下标 i 结尾的子数组的元素的最大的和，也就是这个子数组最后一个元素是下边为 i 的元素，并且这个子数组是所有以 i 结尾的子数组中，和最大的。

这样的话就有两种情况，

• 如果 dp [ i - 1 ] < 0，那么 dp [ i ] = nums [ i ]。
• 如果 dp [ i - 1 ] >= 0，那么 dp [ i ] = dp [ i - 1 ] + nums [ i ]。

publicintmaxSubArray(int[] nums) {
intn=nums.length;
int[] dp=newint[n];
intmax=nums[0];
dp[0] =nums[0];
for (inti=1; i<n; i++) {
//两种情况更新 dp[i]if (dp[i-1] <0) {
dp[i] =nums[i];
        } else {
dp[i] =dp[i-1] +nums[i];
        }
//更新 maxmax=Math.max(max, dp[i]);
    }
returnmax;
}

时间复杂度： O（n）。

空间复杂度：O（n）。

总

解法一和解法二的动态规划，只是在定义的时候一个表示以 i 开头的子数组，一个表示以 i 结尾的子数组，却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和，不如解法二直接，只保存最大的和。