最大连续子序列和问题

最大连续子序列和问题是一个经典的算法问题，在”Data Structures and Algorithm Analysis in C”一书第2章中介绍了此问题，并给出了复杂度从O(n^3)至O(n)的4种解法，这里对此问题稍作扩展总结一下。

问题描述

给定一个数字序列，求出其最大连续子序列和，并给出对应的区间。如给定{-2, 11, -4, 13, -5, -2}，最大子序列和为20，对应的区间为[1, 3]。（下标从0开始）

输出区间中至少包含一个元素，即若输入的数全部为负数，需输出最大的那个负数。

若有多个子序列和相同，返回任意一个子序列区间即可。

函数原型：

int MaxSubsequenceSum(const int A[], int N, int * left, int * right);

其中left及right为输出区间。

注：原始问题中，不需要输出对应区间，且若均为负数输出0，此处进行了一些扩展。

O(n^2)算法

直接循环求解，代码如下：

int MaxSubsequenceSum(const int A[], int N, int * left, int * right) {
  int i, j;
  int maxIndex, maxNum, tmpSum, maxSum;

  maxNum = A[0];
  maxIndex = 0;
  maxSum = 0;
  for (i = 0; i < N; i++) {
    if (A[i] > maxNum) {
      maxIndex = i;
      maxNum = A[i];
    }

    tmpSum = 0;
    for (j = i; j < N; j++) {
      tmpSum += A[j];
      if (tmpSum > maxSum) {
        maxSum = tmpSum;
        *left = i;
        *right = j;
      }
    }
  }

  if (maxNum <= 0) {
    *left = maxIndex;
    *right = maxIndex;
    return maxNum;
  }

  return maxSum;
}

O(nlog(n))算法

二分法递归求解，分成左半部分和右半部分分别求解，有三种可能：最大序列位于左半部分；最大序列位于右半部分；最大序列位于中间。只需要解决最大部分位于中间的情况即可。算法如下：

int MaxSubsequenceSum(const int A[], int N, int * left, int * right) {
  return MaxSubSumIterate(A, 0, N - 1, left, right);
}

int MaxSubSumIterate(const int A[], int Nl,int Nr, int * left, int * right) {
  int leftMax, leftMaxLeft, leftMaxRight;
  int rightMax, rightMaxLeft, rightMaxRight;
  int middleMax, middleMaxLeft, middleMaxRight;
  int tmpSum;
  int center;
  int i;

  /* Base case */
  if (Nl == Nr) {
    *left = Nl;
    *right = Nr;
    return A[Nl];
  }

  /* Left & Right */
  center = (Nl + Nr) / 2;
  leftMax = MaxSubSumIterate(A, Nl, center, &leftMaxLeft, &leftMaxRight);
  rightMax = MaxSubSumIterate(A, center + 1, Nr, &rightMaxLeft, &rightMaxRight);

  /* Middle */
  middleMax = 0;
  tmpSum = 0;
  middleMaxLeft = center + 1;
  middleMaxRight= center;

  for (i = center; i >= Nl; i--) {
    tmpSum += A[i];
    if (tmpSum > middleMax) {
      middleMax = tmpSum;
      middleMaxLeft = i;
    }
  }

  tmpSum = middleMax;
  for (i = center + 1; i <= Nr; i++) {
    tmpSum += A[i];
    if (tmpSum > middleMax) {
      middleMax = tmpSum;
      middleMaxRight = i;
    }
  }

  /* middleMax == 0 说明middle无效 */
  if (middleMax > 0 && middleMax > leftMax && middleMax > rightMax) {
    *left = middleMaxLeft;
    *right = middleMaxRight;
    return middleMax;
  }
  else {
    if (leftMax >= rightMax) {
      *left = leftMaxLeft;
      *right = leftMaxRight;
      return leftMax;
    }
    else {
      *left = rightMaxLeft;
      *right = rightMaxRight;
      return rightMax;
    }
  }
}

O(n)算法

只循环一遍，逐个累加，若累加结果为正，说明需要保留，若结果为负，说明需要丢弃。在这个算法中，数据顺序输入，且无需保留，是解决此问题最完美的算法。代码如下：

int MaxSubsequenceSum3(const int A[], int N, int * left, int * right) {
  int thisSum, maxSum;
  int maxNum, maxIndex;
  int tmpLeft;
  int i;

  tmpLeft = 0;
  thisSum = 0;
  maxNum = A[0];
  maxIndex = 0;
  maxSum = 0;

  for (i = 0; i < N; i++) {
    if (A[i] > maxNum) {
      maxIndex = i;
      maxNum = A[i];
    }

    thisSum += A[i];

    if (thisSum > maxSum) {
      maxSum = thisSum;
      *right = i;
      *left = tmpLeft;
    }
    else if (thisSum < 0) {
      thisSum = 0;
      tmpLeft = i + 1;
    }
  }

  if (maxNum <= 0) {
    *left = maxIndex;
    *right = maxIndex;
    return maxNum;
  }
  else {
    return maxSum;
  }
}

---

注：当序列中有0的时候，上面几个算法输出的区间并不相同

相关文章：

算法探讨——再议经典算法问题：求最大子序列和、绝对值最大子序列和以及其区间
程序员编程艺术：第七章、求连续子数组的最大和
最大连续子序列和