Divide and Conquer Algorithm for Finding the Maximum Subarray - How to also provide the result subarray indexes?

Question

Excuse me, I have an assignment to solve the Maximum Sub Array Problem using the Brute Force Algorithm O(n^2), Divide and Conquer O(nlogn) and Kadane's Algorithm O(n). (My code is different).

"For example, for the sequence of values {−2, 1, −3, 4, −1, 2, 1, −5, 4}, the contiguous sub-array with the largest sum is [4, −1, 2, 1] with sum 6." - From the Wiki Page.

I am done with Kadane's and BruteForce, Where my required output is not just to find the sum, but also the starting index of the found sub-array and the ending index.

My current DivideAndConquer code gets me the correct sum. However, I can't see a way to keep track of my indexes since I implemented it recursively (of course). And I don't know if the only way is to use global variables in this case (I prefer not).. Can you help solve that? Or will I need to change the whole design?

#include <iostream>

int DivideAndConquer(int[], int);

int main()
{
    // Example 1
    //const int MyArraySize = 16;
    //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -> 10, sum = 43

    // Example 2
    const int MyArraySize = 8;
    int MyArray[MyArraySize] = { -2, -5, 6, -2, -3, 1, 5, -6 }; // answer: Index 2 -> 6, sum = 7

    int FinalResult;

    FinalResult = DivideAndConquer(MyArray, MyArraySize);
    std::cout << "Using Divide And Conquer: With O(nlogn) Sum = " << FinalResult << "\n\n";

    system("pause");
    return 0;
}

int DivideAndConquer(int* _myArray, int _myArraySize)
{
    if (_myArraySize == 1)
        return _myArray[0];

    int middle = _myArraySize / 2;
    int Result_LeftPortion = DivideAndConquer(_myArray, middle);
    int Result_RightPortion = DivideAndConquer(_myArray + middle, _myArraySize - middle);

    int LeftSum = -9999;
    int RightSum = -9999;
    int TotalSum = 0;

    for (int i = middle; i < _myArraySize; i++)
    {
        TotalSum += _myArray[i];
        RightSum = TotalSum < RightSum ? RightSum : TotalSum;
    }

    TotalSum = 0;

    for (int i = middle - 1; i >= 0; i--)
    {
        TotalSum += _myArray[i];
        LeftSum = TotalSum < LeftSum ? LeftSum : TotalSum;
    }

    int PartialResult = LeftSum < RightSum ? RightSum : LeftSum;
    int Result= (PartialResult < LeftSum + RightSum ? LeftSum + RightSum : PartialResult);

    return Result;
}

Answer 1

Your algorithm has logical problems and it is not optimal. You are not even using the Result_LeftPortion, Result_RightPortion values. Your final result is always maximum of RightSum, LeftSum and TotalSum of the whole array. The values from all other subarrays gets ignored.

One way solve to solve this problem with divide and conquer is as follows. You should save four values for each subarray:

1. Maximum sum that contains the left element ( s_l )
2. Maximum sum that contains the right element ( s_r )
3. Sum of the whole array ( t )
4. Maximum of above values ( mx )

For the case that you are checking a subarray of size 1 all of these values are equal to the value of that element. When merging two subarrays (sub_left, sub_right) these values will be:

1. s_l = max( sub_left.s_l, sub_left.t + sub_right.s_l )
2. s_r = max( sub_right.s_r, sub_right.t + sub_left.s_r )
3. t = sum( sub_left.t + sub_right.t )
4. mx = max( s_l, s_r, t, sub_right.mx, sub_left.mx, sub_left.r+sub_right.l)

The final result will be the value of mx of the array. For finding the position of the subarray with maximum sum you should keep a right index and left index for each of these values and update them accordingly when you perform merge. Consider this case

sub_left.s_r range is (2,5)
sub_right.t range is (6,10)
if ( sub_right.t + sub_left.s_r > sub_right.s_r )
      s_r range = (2,10)

This is my implementation:

#include <iostream>
using namespace std;

struct node {
    //value, right index, left index
    int value,  r,  l;
    node(int _v, int _r, int _l){
        value = _v;
        r = _r;
        l = _l;
    }
    node (){}

};

struct sub {
    // max node containing left element
    // max node containing right element
    // total node
    // max node
    node s_l, s_r, t, mx;
    sub ( node _l, node _r, node _t, node _mx ){
        s_l = _l;
        s_r = _r;
        t = _t;
        mx = _mx;
    }
    sub(){}
};


sub DivideAndConquer(int* _myArray, int left, int right)
{

    if(right == left){
        node n (_myArray[left],right,left);
        return sub( n, n, n, n);
    }
    int mid = (left+right)/2;
    sub sub_left = DivideAndConquer( _myArray, left, mid);
    sub sub_right = DivideAndConquer( _myArray, mid+1, right);

    sub cur;
    if ( sub_left.t.value + sub_right.s_l.value > sub_left.s_l.value ){
        cur.s_l.value = sub_left.t.value + sub_right.s_l.value;
        cur.s_l.r = sub_right.s_l.r;
        cur.s_l.l = sub_left.s_l.l;
    } else {
        cur.s_l = sub_left.s_l;
    }

    if ( sub_right.t.value + sub_left.s_r.value > sub_right.s_r.value ){
        cur.s_r.value = sub_right.t.value + sub_left.s_r.value;
        cur.s_r.l = sub_left.s_r.l;
        cur.s_r.r = sub_right.s_r.r;
    } else {
        cur.s_r = sub_right.s_r;
    }

    cur.t.value = sub_right.t.value + sub_left.t.value;
    cur.t.r = sub_right.t.r;
    cur.t.l = sub_left.t.l;

    if ( cur.s_r.value >= cur.s_l.value &&
         cur.s_r.value >= cur.t.value &&  
         cur.s_r.value >= sub_left.mx.value &&
         cur.s_r.value >= sub_right.mx.value ){
        cur.mx = cur.s_r;
    } else if ( cur.s_l.value >= cur.s_r.value &&
         cur.s_l.value >= cur.t.value &&  
         cur.s_l.value >= sub_left.mx.value &&
         cur.s_l.value >= sub_right.mx.value ){
        cur.mx = cur.s_l;
    } else if ( sub_left.mx.value >= cur.s_l.value &&
         sub_left.mx.value >= cur.t.value &&  
         sub_left.mx.value >= cur.s_r.value &&
         sub_left.mx.value >= sub_right.mx.value ){
        cur.mx = sub_left.mx;
    } else {
        cur.mx = sub_right.mx;
    }

    if ( sub_left.s_r.value + sub_right.s_l.value > cur.mx.value ){
        cur.mx.value = sub_left.s_r.value + sub_right.s_l.value;
        cur.mx.l = sub_left.s_r.l;
        cur.mx.r = sub_right.s_l.r;
    }
    return cur;
}

int main()
{
    // Example 1
    //const int MyArraySize = 16;
    //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -> 10, sum = 43

    // Example 2
    const int MyArraySize = 8;
    int MyArray[MyArraySize] = { -2, -5, 6, -2, -3, 1, 5, -6 }; // answer: Index 2 -> 6, sum = 7

    sub FinalResult = DivideAndConquer(MyArray, 0,MyArraySize-1);
    std::cout << "Sum = " << FinalResult.mx.value << std::endl;
    std::cout << "( " << FinalResult.mx.l << " , " << FinalResult.mx.r << ")" << std::endl;

 //   system("pause");
    return 0;
}

NOTE: This algorithm runs in O(n) time.