题目描述

给定整数$A_1,A_2,A_3,...,A_n$(可能是负整数)，求${\sum }_{k=i}^j{A}_k$的最大值。如果所有的整数均为负数，那么最大子序列的和为0。

简单$O(N^3)$算法

最简单的算法就是直接穷举搜索，或称蛮力算法。

public static int maxSubsequenceSum(int[] a) {
   int maxSum = 0;
   for (int i = 0; i < a.length; i++) {
       for (int j = i; j < a.length; j++) {
           int thisSum = 0;
           for (int k = i; k <= j; k++)
               thisSum += a[k];
           if (thisSum > maxSum)
               maxSum = thisSum;
       }
   }
   return maxSum;
}

改进的$O(N^2)$算法

我们试图从算法中删除嵌套循环，这样会降低运行时间。改进算法使用${\sum }_{k=i}^j{A}_k=A_j+{\sum }_{k=i}^{j-1}{A}_k$。换句话说就是我们已经计算了子序列$i,...,j-1$的和，那么计算子序列$i,...,j$应该不会花太多时间，我们只需要多家一次计算即可。改进后的算法如下，只使用了两层嵌套循环。运行时间为$O(N^2)$。

public static int maxSubsequenceSum(int[] a) {
    int maxSum = 0;
    for (int i = 0; i < a.length; i++) {
        int thisSum = 0;
        for (int j = i; j < a.length; j++) {
            thisSum += a[j];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

线性算法

我们可以从分析中排除大量可能的子序列。很显然，最大子序列不可能从负数开始，因此，如果$a[i]$为负，那我们可以跳过内循环，并增加$i$。更普遍的，最大子序列不可能以负子序列开始。

public static int maxSubsequenceSum(int[] a) {
    int maxSum = 0;
    int thisSum = 0;
    for (int i = 0, j = 0; j < a.length; j++) {
        thisSum += a[j];
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0) {
            i = j + 1;
            thisSum = 0;
        }
    }
    return maxSum;
}

如果我们检测到和为负数，可以将$i$直接变成$j$。