Başlangıç ​​ve bitiş dizinine sahip alt altdize

Question

Başlatma ve bitiş dizinine sahip bitişik alt dizeyi bulmaya çalışıyorum. Benim kullandığım yöntem, O (nlogn) zaman karmaşıklığı ile bölünme ve fethetmek.

Birkaç test vakasıyla test ettim ve başlangıç ​​ve bitiş indeksi her zaman doğru çalışıyor. Bununla birlikte, dizi tek sayı içeren öğeler içeriyorsa, 'u buldum, maksimum toplam değeri bazen doğru, bazen yanlış (rastgele görünüyor). Ancak, durumlar için, her zaman doğrudur.

int maxSubSeq(int A[], int n, int &s, int &e) 
{ 
    // s and e stands for start and end index respectively, 
    // and both are passed by reference 

    if(n == 1){ 
     return A[0]; 
    } 

    int sum = 0; 
    int midIndex = n/2; 
    int maxLeftIndex = midIndex - 1; 
    int maxRightIndex = midIndex; 

    int leftMaxSubSeq = A[maxLeftIndex]; 
    int rightMaxSubSeq = A[maxRightIndex]; 

    int left = maxSubSeq(A, midIndex, s, e); 
    int right = maxSubSeq(A + midIndex, n - midIndex, s, e); 

    for(int i = midIndex - 1; i >= 0; i--){ 
     sum += A[i]; 
     if(sum > leftMaxSubSeq){ 
      leftMaxSubSeq = sum; 
      s = i; 
     } 
    } 
    sum = 0; 
    for(int i = midIndex; i < n; i++){ 
     sum += A[i]; 
     if(sum > rightMaxSubSeq){ 
      rightMaxSubSeq = sum; 
      e = i; 
     } 
    } 

    return max(max(leftMaxSubSeq + rightMaxSubSeq, left),right); 
} 

Aşağıda ben, tek tek sayılı öğesi vardır, biri çift sayılı olan elemanlar ile çalışıyordu test durumları ikidir: İşte benim kodudur.

Array with 11 elements: 
    1, 3, -7, 9, 6, 3, -2, 4, -1, -9, 
    2, 
Array with 20 elements: 
    1, 3, 2, -2, 4, 5, -9, -4, -8, 6, 
    5, 9, 7, -1, 5, -2, 6, 4, -3, -1, 

Düzenleme: çıkışların 2 çeşit şunlardır: Bu oluşmasını neden

// TEST 1 
Test file : T2-Data-1.txt 
Array with 11 elements: 
    1, 3, -7, 9, 6, 3, -2, 4, -1, -9, 
    2, 

maxSubSeq : A[3..7] = 32769 // Index is correct, but sum should be 20 

Test file : T2-Data-2.txt 
Array with 20 elements: 
    1, 3, 2, -2, 4, 5, -9, -4, -8, 6, 
    5, 9, 7, -1, 5, -2, 6, 4, -3, -1, 

maxSubSeq : A[9..17] = 39 // correct 

// TEST 2 

Test file : T2-Data-1.txt 
Array with 11 elements: 
    1, 3, -7, 9, 6, 3, -2, 4, -1, -9, 
    2, 

maxSubSeq : A[3..7] = 20 

Test file : T2-Data-2.txt 
Array with 20 elements: 
    1, 3, 2, -2, 4, 5, -9, -4, -8, 6, 
    5, 9, 7, -1, 5, -2, 6, 4, -3, -1, 


maxSubSeq : A[9..17] = 39 

herkes gösterebilir misiniz? Şimdiden teşekkürler!

Answer 1

n senin dizinin doğru boyutu (bunu bir parametre olarak geçirilen ve daha sonra midIndex başlatmak için kullanılan ama biz gerçek çağırmayı görüyorum ve böylece yaptığınızı varsayalım gerekir ediliyor bkz olduğunu varsayarsak doğru), konu burada yatıyor: diziniz biz

olarak temsil edebilir elemanların tek sayıda olması durumunda

int midIndex = n/2;

biz orta endeks hep

(2k + 1)/2 = k + (1/2) denk olacağı bulabilirsiniz

demektir n = 2k Her tam sayı için k, her zaman k'a eklenen bir tamsayı sayısının yarısına sahip olursunuz.

C++, kayan nokta sayıları alan tamsayıları döndürmez; o kırpıyor. Yani k + 0.5k + 1'u beklerken, kesilmeden sonra aslında k elde edersiniz.

Bu, örneğin, dizi boyutunuzun 11, midIndex'un olarak tanımlandığı anlamına gelir. Bu nedenle, kodunuzu buna göre ayarlamanız gerekir.