Ниже приведен пример кода на 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 вместо фактического отрицательного значения? Я искал в Интернете объяснение базового случая и постановку задачи, но не смог найти объяснение.
Пустая последовательность {}
является подпоследовательностью {x}
и его сумма равна 0. Сумма последовательности {x}
это х, который, очевидно, меньше 0, если х отрицателен.