问题描述

在长度为N的整形数组中,求连续子串的和的最大值。

例如:1 2 4 5 -11 5 -3,结果为6。

注意:要考虑到数组中元素都为负数的情况。

O(n)解法

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int maxSubSum(int[] a) {
int maxSum = a[0];
int curSum = 0;
for (int j = 0; j < a.length; j++) {
curSum += a[j];
if (curSum > maxSum) {
maxSum = curSum;
} else if (curSum < 0) {
curSum = 0;
}
}
return maxSum;
}

本算法的关键在于,对于一个子序列,如果其和为负数,则不可能作为最大子串的前缀。