Алгоритм возврата максимально возможной суммы подпоследовательностей в последовательности

Question

int maxSumRec(const vector<int> &a, int left, int right){

    if (left == right){

               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 leftBorderSum = 0; int leftBorderMax = 0; 
    for (int i = center; i >= left; i--){

        leftBorderSum += a[i];
        if (leftBorderSum > leftBorderMax){

            leftBorderMax = leftBorderSum;
        }
    }

    int rightBorderSum = 0; int rightBorderMax = 0;
    for (int i = center+1; i <= right; i++){

        rightBorderSum += a[i];
        if (rightBorderSum > rightBorderMax){

            rightBorderMax = rightBorderSum;
        }

    }

    int crossSum = rightBorderMax + leftBorderMax;

    return max3(maxLeftSum, maxRightSum, crossSum);

}

Это алгоритм O (NlogN), я знаю, что он не самый лучший. Но просто задайте несколько вопросов:

1. в первом операторе if, зачем возвращать 0, если a [left] <0? </p>

2. зачем нужны 2 для петель? не логика, подобная этой, найдите максимум первой половины и второй половины, а затем добавьте их, чтобы увидеть, больше ли дополнение, чем то или другое. если это так, то мы можем сразу перейти к последним 2 строкам?

Большое спасибо,

Юэ Харриет

Answer 1

1. в первом операторе if, зачем возвращать 0, если a [left] <0? </li>

Потому что тогда пустая подпоследовательность имеет максимальную сумму, равную 0.

Answer 2

Хорошо, я разобрался со вторым вопросом, потому что мы должны позаботиться о последовательных терминах, а не о прыжковых.