Algoritma bir sıradaki olası en yüksek toplamları toplamına döndürme

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

} 

Bu bir O (NlogN) algoritmasıdır, en iyisi olmadığını biliyorum. Bir [sol] < 0 eğer deyim, neden 0 dönerseniz

1. ilk: Ama sadece üzerinde birkaç soru var?

2. Neden 2 döngü için gerekir? Böyle bir mantık değil, ilk yarının ve ikinci yarının maksimumu bulun ve sonra ekleme işleminin her ikisinden de büyük olup olmadığını görmek için ekleyin. Bu durumda , o zaman doğrudan son 2 satıra atlayabiliriz? Biz atlayarak terimlerin yerine ardışık terimlerin bakmak zorunda çünkü

Çok teşekkürler,

Yue Harriet

Answer 1

ilk
1. bir [sol] < 0 eğer deyim, neden 0 dönerseniz?

sonra boş altdizi bu proje Euler soru olduğu 0

Answer 2

Tamam, ben 2 soru çözdüm.