解决这个问题还可以用动态规划技巧解决，但是 dp 数组的定义比较特殊。按照我们常规的动态规划思路，一般是这样定义 dp 数组：
nums[0..i] 中的「最大的子数组和」为 dp[i]。
Warning
连续子数组： 比如[1,2,3], 连续子数组有[1,2],[2,3],[1,2,3], 其中[1,3]不是连续的
然后类比：[1,3,5]这种非相邻数组，[1,3]、[3,5]、[1,3,5]是连续的，而[1,5]不是 如果这样定义的话，整个nums数组的「最大子数组和」就是dp[n-1]。如何找状态转移方程呢？按照数学归纳法，假设我们知道了dp[i-1]，如何推导出dp[i]呢？
如下图，按照我们刚才对 dp 数组的定义，dp[i] = 5 ，也就是等于 nums[0..i] 中的最大子数组和：
那么在上图这种情况中，利用数学归纳法，你能用 dp[i] 推出 dp[i+1] 吗？
实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums[0..i] 中的最大子数组与 nums[i+1] 是相邻的，也就没办法从 dp[i] 推导出 dp[i+1]。
比如上图 dp[i]不包括-6，自然无法推导出 dp[i+1], 如何 dp[i+1]需要这个-6 呢？
所以说我们这样定义 dp 数组是不正确的，无法得到合适的状态转移方程。对于这类子数组问题，我们就要重新定义 dp 数组的含义：
以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
Tip
nums[i-1]必定与 dp[i]相邻，然后我们只要判断 dp[i-1]+num[i-1]和 num[i-1]大小即可，谁大就用谁，dp[i-1]+num [i-1](带上了 num [i-1]，就必定与 nums[i]相邻，若 num[i-1]，说明前面的加起来还没有 num[i-1]大，舍弃即可，从 num[i-1]开始重新寻找) 大，
这种定义之下，想得到整个 nums 数组的「最大子数组和」，不能直接返回 dp[n-1]，而需要遍历整个 dp 数组：
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;依然使用数学归纳法来找状态转移关系：假设我们已经算出了 dp[i-1]，如何推导出 dp[i] 呢？
可以做到，dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
如何选择？既然要求「最大子数组和」，当然选择结果更大的那个啦：
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);综上，我们已经写出了状态转移方程，就可以直接写出解法了：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
int[] dp = new int[n];
// base case
// 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}动态规划设计：最大子数组 | labuladong 的算法笔记
以上解法时间复杂度是 O(N)，空间复杂度也是 O(N)，较暴力解法已经很优秀了，不过注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，那么我们可以施展前文 动态规划的降维打击：空间压缩技巧 讲的技巧进行进一步优化，将空间复杂度降低：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
// dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}