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 に答える