| 日期 | 是否一次通过 | comment |
|---|---|---|
| 2019-01-26 13:20 | N | 实质是preOrder + swap |
| 2019-01-27 13:20 | Y | |
| 2019-05-15 13:20 | N | 初值从1开始，哎 |
| 2020-02-22 22:57 | N | 递推公式错误，写成了Res(A[i]) = max(Res(A[i-1])+A[i], Res(A[i-1]))
|
题目：{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)
解释：
image.png
图片来源：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
问题拆解：
- 给定一个数组A，求任意位置i的连续子数组最大和 （[ A[0], A[i] ]）:
Res(A[i]) = max(Res(A[i-1])+A[i], A[i]) :
A[i]的连续子数组最大和 == max(A[i]的连续子数组最大和+A[i], A[i] )
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int locMax = array[0];
int gloMax = array[0];
for(int i=1; i<array.length; i++) { // 注意，初始从1开始（因为0已经被赋为初值了）
locMax = Math.max(locMax+array[i], array[i]);
gloMax = Math.max(gloMax, locMax);
}
return gloMax;
}
}
如果要输出连续子数组最大和，以及对应的最大数组长度：
public int[] maxSubArraySum(int[] arr) {
int globalMax = arr[0], localMax = arr[0], glbSta = 0, glbEnd = 0, locSta = 0;
for (int i = 1; i < arr.length; i++) {
if (localMax < 0) { // 丢弃之前的累加和（负的只没用）；只有这个时候最大连续子数组起点会变
localMax = 0;
locSta = i;
}
localMax += arr[i];
if (globalMax < localMax) {
globalMax = localMax;
glbSta = locSta;
glbEnd = i;
}
if(globalMax == localMax && glbEnd - glbSta < i - locSta) {
glbSta = locSta;
glbEnd = i;
}
}
return new int[]{globalMax, glbSta, glbEnd};
}
