【本文版权归微信公众号"代码艺术"（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】
题目
输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
举例
输入：2, -3, 4, 5, -9
输出：9
和最大的连续子数组是 {4, 5}，结果就是9。
思路
我们先假设和最大连续子数组是从第一个数开始的。初始化和为0。第一步是加上数字2，此时和为2。第二步加上数字-3，此时和为-1。那么问题来了，我们到底要不要加上数字-3呢？分析过程如下：
- 加上-3。此时的和为-1，然后由-1继续加下一个数。
- 不加-3。也就是意味当前连续子数组就终结于-3之前的数字，下一个连续子数组的和初始化为0，再加上第一个数字-3，和为-3。
由上述分析可知，加上-3，此时累加的子数组和是-1；不加-3，此时累加的子数组和是-3。-1大于-3，为了后续的累加和更大，所以选择加上-3。
接下来，第三步要不要加上数字4，我们依据上面的决策流程继续分析。当加上数字4，此时累加和为4-1=3；不加上数字4，意味着当前连续子数组终结于数字4之前，此时的累加和初始化为0，加上数字4后和等于4。显而易见，4大于3，所以我们选择抛弃前面的累加和，由数字4继续开始。
后续步骤省略，总结一番。当我们遍历数组时，对于每个数字，要么与前面的子数组累加，要么作为新子数组的起点，如果累加之后的子数组和小于（或等于）当前数字，我们就选择抛弃前面的累加和，将当前数字作为新子数组的起点。整个过程可以用表格总结如下：
| 步骤 | 操作 | 累加的子数组和 | 最大的子数组和 |
|---|---|---|---|
| 1 | 加2 | 2 | 2 |
| 2 | 加-3 | -1 | 2 |
| 3 | 抛弃累加的和-1，加4 | 4 | 4 |
| 4 | 加5 | 9 | 9 |
| 5 | 加-9 | 0 | 9 |
代码
根据题目要求，我们只需要求出连续子数组的最大和，如果面试官还要求找到连续子数组的起点与终点下标，那么最终的java代码如下：
public class Main {
public static int child_sum(int[] arr) {
if (arr == null || arr.length < 1) {
return 0;
}
int left0 = 0;
int left1 = 0;
int right = 0;
int max = arr[0];
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum <= arr[i]) { //使用<=还是<呢？
sum = arr[i];
left0 = i;
}
if (sum > max) {
max = sum;
left1 = left0;
right = i;
}
}
System.out.println("left:" + left1 + " right:" + right + " max:" + max);
return max;
}
public static void main(String[] args) {
int[] arr1 = new int[]{2, -3, 4, 5, -9};
int[] arr2 = new int[]{2, -2, 4, 5, -9};
int[] arr3 = new int[]{-2, -3, -4, -5, -9};
child_sum(arr1);
child_sum(arr2);
child_sum(arr3);
}
}
打印输出：
left:2 right:3 max:9
left:2 right:3 max:9
left:0 right:0 max:-2
在上面的代码中使用小于等于或者使用小于有什么区别呢？
假设数组为{2, -2, 4, 5, -9}，如果判断条件是小于等于当前数字，那么所得的最大连续子数组为{4, 5}。如果判断条件是小于当前数字，那么所得的最大连续子数组为{-2, 2, 4, 5}。如果对最大连续子数组的长度没有明确要求，使用小于等于进行判断即可。
版权声明
【本文版权归微信公众号"代码艺术"（ID：onblog）所有，若是转载请务必保留本段原创声明，违者必究。若是文章有不足之处，欢迎关注微信公众号私信与我进行交流！】
