题⽬描述
输⼊⼀个⻓度为n 的整型数组array ，数组中的⼀个或连续多个整数组成⼀个⼦数组，找到⼀个具有
最⼤和的连续⼦数组。
- ⼦数组是连续的，⽐如[1,3,5,7,9] 的⼦数组有[1,3] ， [3,5,7] 等等，但是[1,3,7] 不是⼦数组
- 如果存在多个最⼤和的连续⼦数组，那么返回其中⻓度最⻓的，该题数据保证这个最⻓的只存在⼀个
- 该题定义的⼦数组的最⼩⻓度为1 ，不存在为空的⼦数组，即不存在[]是某个数组的⼦数组
- 返回的数组不计⼊空间复杂度计算
示例 1
输⼊：[1,-2,3,10,-4,7,2,-5]
返回值：[3,10,-4,7,2]
说明：经分析可知，输⼊数组的⼦数组[3,10,-4,7,2]可以求得最⼤和为18，故返回[3,10,-4,7,2]
示例 2
输⼊：[1]
返回值：[1]
思路及解答
这道题是⽐较经典的动态规划，假设现在有 n 个元素，突然加上⼀个元素，变成 n+1 个元素，对连续⼦数组的最⼤和有什么影响呢？
我们只需要知道以每⼀个元素结尾的最⼤连续⼦数组，再维护⼀个最⼤的值即可。
假设数组为num[] ，⽤ dp[i] 表示以下标 i 为终点的最⼤连续⼦数组和，遍历每⼀个新的元素nums[i+1] ，以 num[i+1] 为连续⼦数组的情况只有两种：
- dp[i] + num[i+1]
- 只有num[i+1]
所以以nums[n] 结尾的最⼤连续⼦数组和为： dp[i] = max( dp[i-1] + num[i], num[i])
在计算的过程中，需要维护⼀个最⼤的值，并且把该连续⼦数组的左边界以及右边界维护好，最后根据维护的区间返回。
public class Solution85 {
public int[] FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
dp[0] = array[0];
int maxsum = dp[0];
int left = 0, right = 0;
int maxLeft = 0, maxRight = 0;
for (int i = 1; i < array.length; i++) {
right++;
dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
if (dp[i - 1] + array[i] < array[i]) {
left = right;
}
// 更新最⼤值以及更新最⼤和的⼦数组的边界
if (dp[i] > maxsum || dp[i] == maxsum && (right - left + 1) > (maxRight - maxLeft + 1)) {
maxsum = dp[i];
maxLeft = left;
maxRight = right;
}
}
// 保存结果
int[] res = new int[maxRight - maxLeft + 1];
for (int i = maxLeft, j = 0; i <= maxRight; i++, j++) {
res[j] = array[i];
}
return res;
}
}