---

问题#

最大子序列问题

方案一#

思路##

先搜寻出所有的子序列，然后求和比较

代码##

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开始，但是对于最大子序列，其起始位子的值不可能为负数；进一步看，如果最大子序列是Ai_{Aj，对于任意i<p<j，最大子序列的子序列Ai}Ap的和一定大于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）。仅需要常量空间并以线性时间运行的联机算法几乎是完美的。