Algorithmus, um die maximal mögliche Summe von Untersequenzen in einer Sequenz

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); 

} 

Dies ist ein O (NlogN) Algorithmus, ich weiß, es ist nicht der beste. Aber haben nur einige Fragen dazu:

1. in der ersten if-Anweisung, warum 0 zurückgeben, wenn eine [links] < 0?

2. warum brauchen die 2 for loops? ist nicht die Logik wie diese, finden Sie das Maximum der ersten Hälfte und der zweiten Hälfte, und fügen Sie sie dann hinzu, um zu sehen, ob die Addition größer ist als beide. Wenn es in diesem Fall ist, können wir direkt zu den letzten 2 Zeilen springen?

Vielen Dank,

Yue Harriet

Answer 1

1. in dem ersten if-Anweisung, warum 0 zurückgeben, wenn ein [links] < 0?

Denn dann die leere Teilfolge die maximale Summe hat, die 0.

Answer 2

OK, dachte ich, die zweite Frage aus, weil wir kümmern uns um Konsekutivbegriffe statt Springen Bezug zu nehmen.