Print Max Subarray Values From An Array After Running Divide And Conquer Algorithm

Question

I have implemented a solution to find the maximum subarray from an array of values. I can print out the full array prior to running my divide and conquer algorithm, but I cannot seem to figure out how to print the subarray after the algorithm is run.

int newArray[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};

int arraySize = (sizeof(newArray)/sizeof(int));

printArray(newArray, 0, arraySize - 1);

int total = maxSubDiv(newArray, 0, arraySize - 1);

This is a snippet of my main function. I am using a printArray function to print the full array prior to finding the maximum subarray. The maxSubDiv function is as follows:

int maxSubDiv(int * Array1, int left, int right)
{
    if(left == right)
    {
        return Array1[1];
    }

    int middle = (left + right)/2;

    return findMax(maxSubDiv(Array1, left, middle), maxSubDiv(Array1, middle + 1, right), leftRightCross(Array1, left, middle, right));

}

int leftRightCross(int * Array1, int left, int middle, int right)
{
    int sum = 0;

    int leftSum = INT_MIN;

    for(int i = middle; i >= left; i--)
    {
        sum = sum + Array1[i];
        if(sum > leftSum)
        {
            leftSum = sum;
        }
    }

    sum = 0;
    int rightSum = INT_MIN;

    for(int i = middle + 1; i <= right; i++)
    {
        sum = sum + Array1[i];
        if(sum > rightSum)
        {
            rightSum = sum;
        }
    }

    sum = leftSum + rightSum;

    return sum;
}

The algorithm seems to test well, but I am just having trouble printing out the subarray that contains the integers of the max subarray. Any help is much appreciated!

struct tuple{

    int begin;
    int end;
    int length;

};

int findMax(int left, int right, int cross)
{

    int max;
    if(left > right && left > cross)
    {
        max = left;
    }

    else if(right > left && right > cross)
    {
        max = right;
    }

    else
    {
        max = cross;
    }

    return(left, right, cross);
}

Eric Z Eric Z · Accepted Answer · 2015-10-15T04:19:10

In maxSubDiv() when you compare the max of three subarrays, return tuple (begin, end, length) of the max subarray instead of just the length. "begin", "end" specifies the range of the max subarray, which you can leverage later for print. You should also return (begin, end, length) from leftRightCross().

E.g.,

// pesudocode
if max is left:
   return (left_begin, left_end, left_length)
if max is right:
   return (right_begin, right_end, right_length)
if max is middle:
   return (middle_begin, middle_end, middle_length)

The tuple can be implemented in struct in C.

Print Max Subarray Values From An Array After Running Divide And Conquer Algorithm

1 Answers