주어진 시퀀스에서 최대 서브 시퀀스를 찾는 재귀 적 솔루션의 기본 케이스가 음수이면 0을 반환하는 이유는 무엇입니까?

Question

다음은 최대 서브 시퀀스 문제를 해결하기 위해 재귀를 사용하여 작성된 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을 반환하면 합계에 영향을 미치지 않을까요? 나는 인터넷을 검색하여 기본 사례와 문제 진술에 대한 설명을 찾았지만 설명을 찾을 수 없었다.

Answer 1

빈 시퀀스 {x}의 서브 시퀀스이며 그 합은 0입니다. {x} 시퀀스의 합은 x이며, x가 음수이면 분명히 0보다 작습니다.