问题#
方案一#
思路##
先搜寻出所有的子序列，然后求和比较
代码##
public static void maxSubSum1(int[] a) {
int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int tempSum = 0;
for (int k = i; k <= j; k++) {
tempSum += a[k];
}
if (maxSum < tempSum) {
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}
System.out.println("this subsequence is from " + startIndex + " to " + endIndex + ", max sum is " + maxSum);
}
结果##
分析##
此方案用了三层循环，第一层循环确定子序列的起始位子（i），第二层循环确定子序列的终止位子（j）。通过第一层循环和第二层循环确定所有的子序列，然后再通过第三层循环求和。最后比较子序列的和，确定起始位子和终止位子。
此方案的时间复杂度为O(N^3 )，这完全取决于第三层for循环。所以为了提高效率，我们可以撤除第三层for循环（当然不是所有的三层循环都能这么做）。
方案二#
思路##查询
搜索出所有的子序列，然后求和比较。（相对于方案一，去除了第三层求和的for循环）
代码##
public static void maxSubSum2(int[] a) {
int maxSum = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < a.length; i++) {
int tempSum = 0;
for (int j = i; j < a.length; j++) {
tempSum += a[j];
if (maxSum < tempSum) {
maxSum = tempSum;
startIndex = i;
endIndex = j;
}
}
}
System.out.println("this subsequence is from " + startIndex + " to " + endIndex + ", max sum is " + maxSum);
}
分析##
此方案用了三层循环，第一层循环确定子序列的起始位子，第二层循环确定子序列的终止位子。通过第一层循环和第二层循环确定所有的子序列，然后通过第二层for循环求和。时间复杂度为O(N^2)。
方案三#
思路##
方案一和方案二的第一层循环用来确定子序列的起始位子，第二层循环用来确定子序列的结束位子。从两层循环的起始位子看，都是从0开始，但是对于最大子序列，其起始位子的值不可能为负数；进一步看，如果最大子序列是AiAj，对于任意i<p<j，最大子序列的子序列AiAp的和一定大于0，所以对于任意从起始位子开始的子序列，若其和为负数，则丢弃，i继续向前推进，直到数列遍历完毕。
代码##
public static void maxSubSum3(int a[]) {
int maxSum = 0, thisSum = 0;
for (int j = 0; j < a.length; j++) {
thisSum += a[j];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
System.out.println(maxSum);
}
分析##
此方法对于i（子序列的其实位子）进行了优化，因为我们关注的只是最大子序列，所以不必搜寻出所有的子序列（和方案一、方案二的区别），只需找到所有Ai~Ap（i<p<j）的和不为负数的子序列，然而这种方式只需要一层循环即可，所以去掉了最外层的循环。然后求出这些子序列的和，然后比较。此算法的时间复杂度为O(N)。
该算法的一个附加优点是，它对数据只进行一次扫描，一旦a[i]被读入处理，就不需要被记忆。因此，如果数组在磁盘上或通过互联网传播，那么它就可以被按顺序读入，在内存中就不必存储数组的任何部分。不仅如此，在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。具有这种 特性的算法叫做联机算法（on-line algrithm）。仅需要常量空间并以线性时间运行的联机算法几乎是完美的。
