Макс. Подмассива с индексом начала и конца

Question

Я пытаюсь найти максимальный непрерывный подмассива с индексом начала и конца. Метод, который я принял, делит и управляет с временной сложностью O (nlogn).

Я тестировал несколько тестовых примеров, и индекс начала и конца всегда работал правильно. Однако я обнаружил, что , если массив содержит нечетные числа элементов, максимальная сумма иногда правильная, иногда некорректная (по-видимому, случайная). Но для четных случаев это всегда правильно. Вот мой код:

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

Ниже два из тестовых случаев я работал с, один имеет нечетные элементы, один даже пронумерованных элементов.

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, 

Edit: Ниже приведены 2 вида выходов:

// 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 

Может ли указать, почему это происходит? Заранее спасибо!

Answer 1

Предполагая, чтоn правильный размер вашего массива (мы видим, что передается в качестве параметра, а затем используется для инициализации midIndex но мы не увидеть его фактический вызов и поэтому должны считать, что вы делаете это правильно), проблема лежит здесь:

int midIndex = n/2;

В случае, если ваш массив имеет нечетное число элементов, которые можно представить в виде

п = 2k + 1

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

(2k + 1)/2 = к + (1/2)

, что означает что для каждого целого числа, k, вы всегда будете иметь половину целого числа, добавленного к k.

C++ не округляет целые числа, которые получают числа с плавающей запятой; он усекает. Поэтому, пока вы ожидали бы k + 0,5 до раунда до k + 1, вы фактически получаете k после усечения.

Это означает, что, например, когда размер вашей матрицы равен 11, midIndex определяется как . Поэтому вам необходимо соответствующим образом скорректировать код.