シーケンス内のサブシーケンスの可能な最大和を返すアルゴリズム

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）アルゴリズムであり、最適ではないことがわかっています。 [左] < 0を場合ステートメントは、なぜ0を返す場合

1. 最初に：しかし、ちょうどその上にいくつかの質問がありますか？

2. なぜ2 forループが必要ですか？このような論理ではなく、前半と後半の最大値を見つけて加算し、加算値がどちらか大きいかどうかを確認します。 この場合、最後の2行に直接ジャンプできますか？我々はジャンプ用語の代わりに、連続した用語の世話をする必要があるため

おかげで非常に多く、

越ハリエットは

Answer 1

1. if文ならば、なぜ[左] < 0 0を返しますか？

空のサブシーケンスは0

Answer 2

OK、私は、第二の問題を考え出しました。最初の