Макс подмассива с начальным и конечным индексом

Я пытаюсь найти максимальный непрерывный подмассив с начальным и конечным индексом. Я выбрал метод «разделяй и властвуй» с 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,

Редактировать: Ниже приведены 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

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