CODEWITHSUNDEEP
c++algorithmdivide-and-conquer
Tony Tarng
Tony Tarng

Reputation: 749

Max subarray with start and end index

I'm trying to find the maximum contiguous subarray with start and end index. The method I've adopted is divide-and-conquer, with O(nlogn) time complexity.

I have tested with several test cases, and the start and end index always work correctly. However, I found that if the array contains an odd-numbered of elements, the maximum sum is sometimes correct, sometimes incorrect(seemingly random). But for even cases, it is always correct. Here is my code:

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

Below is two of the test cases I was working with, one has odd-numbered elements, one has even-numbered elements.

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: The following are the 2 kinds of outputs:

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

Can anyone point out why this is occurring? Thanks in advance!

Upvotes: 0

Views: 1517

Answers (1)

8protons
8protons

Reputation: 3959

Assuming that n is the correct size of your array (we see it being passed in as a parameter and later used to initialize midIndexbut we do not see its actual invocation and so must assume you're doing it correctly), the issue lies here:

int midIndex = n / 2;

In the case that your array has an odd number of elements, which we can represented as

n = 2k + 1

we can find that your middle index will always equate to

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

which means that for every integer, k, you'll always have half of an integer number added to k.

C++ doesn't round integers that receive floating-point numbers; it truncates. So while you'd expect k + 0.5 to round to k+1, you actually get k after truncation.

This means that, for example, when your array size is 11, midIndex is defined to be 5. Therefore, you need to adjust your code accordingly.

Upvotes: 1

Related Questions