0

下面是使用递归编写的用于解决最大子序列问题的 C++ 示例代码 - 不完全是子序列，而是最大子序列的总和。

int maxSumRec( const vector<int> & a, int left, int right )
{
  if( left == right ) // Base case
    if( a[ left]>0)
      return a[ left ];
    else
      return 0;

  int center = ( left + right ) / 2;
  int maxLeftSum = maxSumRec( a, left, center );
  int maxRightSum = maxSumRec( a, center + 1, right );
  int maxLeftBorderSum = 0, leftBorderSum = 0;
  for( int i = center; i >= left; --i )
  {
    leftBorderSum += a[ i ];
    if( leftBorderSum > maxLeftBorderSum )
      maxLeftBorderSum = leftBorderSum;
  }
  int maxRightBorderSum = 0, rightBorderSum = 0;
  for( int j = center + 1; j <= right; ++j )
  {
    rightBorderSum += a[ j ];
    if( rightBorderSum > maxRightBorderSum )
      maxRightBorderSum = rightBorderSum;
  }
  return max3( maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum );
}

如果剩下的单个元素是负数，为什么基本情况必须返回 0？如果我们返回更高的值 0 而不是实际的负值，它不会影响总和吗？我在互联网上搜索了基本案例和问题陈述的解释，但找不到解释。

4

1 回答 1

1

空序列{}是 的子序列{x}，其和为 0。序列之和{x}为 x，如果 x 为负数，则显然小于 0。

于 2014-07-12T10:30:05.573 回答