Почему базовый случай в рекурсивном решении для поиска максимальной подпоследовательности в данной последовательности возвращает 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 вместо фактического отрицательного значения? Я искал в Интернете объяснение базового случая и постановку задачи, но не смог найти объяснение.

0

Решение

Пустая последовательность {} является подпоследовательностью {x}и его сумма равна 0. Сумма последовательности {x} это х, который, очевидно, меньше 0, если х отрицателен.

1

Другие решения


По вопросам рекламы [email protected]