『算法』最大子序列和的三种算法

最大子序列和问题是算法中一个经典问题了，不同的算法时间复杂度相差甚大。

最大子序列和

给出一组整数，求出这组数字子序列和中的最大值。

算法

• 穷举法

这个是最容易想到的，枚举每一个子序列的大小，记录下最大的和返回。

public static int maxSubSum1(int[] seq) {
      int maxSum = 0;
      int thisSum = 0;
      int len = seq.length;
      for (int i = 0; i < len; i++) {
          thisSum = 0;  //这里要归零
          for (int j = i; j < len; j++) {
            thisSum += seq[j];
            if (thisSum > maxSum)
                maxSum = thisSum;
          }
      }
      return maxSum;
  }

这个比较好理解，枚举出每一个子序列，将最大和记录并返回。
其时间复杂度为O(n^2),但是数据量大了后算法效率很低。

• 分治法

分治法：将一个问题拆分成多个相似的小问题，并对其分别求解，如果拆出的问题依然复杂，就通过递归调用再次将子问题拆分，直到拆出的方法可以以简单方式求得解，最后合并多个小问题的解，就是原问题的结果。
比如下面这段代码：

    public static int maxSubSum(int[] seq, int left, int right) {
        int maxLeftSum = 0;
        int maxRightSum = 0;
        int leftBorderSum = 0;// 左半边包含最右一位数的和
        int rightBorderSum = 0;// 右半边包含最左一位数的和
        int maxLeftBorderSum = 0;
        int maxRightBorderSum = 0;
        /* 只有一个元素 */
        if (left == right) {
            if (seq[left] > 0) {
                return seq[0];
            } else {
                return 0;
            }
        }
        int center = (left + right) / 2;
        maxLeftSum = maxSubSum(seq, left, center);
        maxRightSum = maxSubSum(seq, center + 1, right);
        /* 左半边最大和 */
        for (int i = center; i >= left; i--) {
            leftBorderSum += seq[i];
            if (leftBorderSum > maxLeftBorderSum)
                maxLeftBorderSum = leftBorderSum;
        }
        /* 右半边最大和 */
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += seq[i];
            if (rightBorderSum > maxRightBorderSum)
                maxRightBorderSum = rightBorderSum;
        }
        /* 返回三个值中的最大值 */
        return Math.max(maxLeftBorderSum + maxRightBorderSum, Math.max(maxLeftSum, maxRightSum));
    }

这个算法比较长，但是效率高了很多，时间复杂度是O(NlogN)。思路：

1. 方法传入序列数组，左右两边索引。
2. 如果只有一个元素，大于零返回自己，否则返回零。
3. 获得中间索引，用于将当前的序列数组分隔为两份，“分而治之”。
4. 通过递归调用自身方法获得分隔出的两个子序列最大值。
5. 两个for循环是获得两个子序列包含从分割处开始向两边求和，得出子序列的最大和。
   这样可以通过将这两个子序列相加，得到整个序列的最大子序列和。
6. 将左序列最大子序列和、右序列最大子序列和、包含分割的子序列和（两个for结果的和）比较，最大的为所求值。

• 贪心算法

贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。，再递推到全局。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
对于最大子序列问题，算法如下：

public static int maxSubSum(int[] seq) {
    int maxSum = 0;
    int thisSum = 0;
    for (int i = 0; i < seq.length; i++) {
        thisSum += seq[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) {
            thisSum = 0;
        }
    }
    return maxSum;
}

这个算法，难理解主要在else if (thisSum < 0) thisSum = 0;这里。
我们知道，任何一个最大子序列和，它的第一位都不会是负数。结合贪心算法的定义，当thisSum小于零时，即使加上后面的数也不会是最大子序列和（不如直接不要当前的thisSum），所以直接将thisSum设为0，重新开始计算新的子序列和。
这个算法的时间复杂度为O(N)，相对于第一种穷举法，效率高了很多。

<br /><br />

---

文章内容为个人理解，如有错误欢迎指出。

邮箱：CodingDjz@126.com