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

Can you have another output variable (by reference) at your recursive function? — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Sep 6, 2016 at 13:07
@πάνταῥεῖ Yes. Something like return Tuple<int, int*, int*> or & is completely fine. But I still can't see how can I keep track of the indexes since I am not doing it iteratively.. — Khalil Khalaf
– Khalil Khalaf, Commented Sep 6, 2016 at 13:09
@πάνταῥεῖ The factory thing or the suggested return Tuple<..>? — Khalil Khalaf
– Khalil Khalaf, Commented Sep 6, 2016 at 13:10
No its logic is not right. I am writing a complete answer right now. — Saeid
– Saeid, Commented Sep 6, 2016 at 15:26

Khalil Khalaf · Accepted Answer · 2016-09-06 17:36:12Z

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:

Maximum sum that contains the left element ( s_l )
Maximum sum that contains the right element ( s_r )
Sum of the whole array ( t )
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:

s_l = max( sub_left.s_l, sub_left.t + sub_right.s_l )
s_r = max( sub_right.s_r, sub_right.t + sub_left.s_r )
t = sum( sub_left.t + sub_right.t )
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.

This definitely deserves more upvotes. It highlights a logical error in my code (which I though it was perfect), it provides a design for the correct approach, it provides a design for solving my problem and not just the original problem (my problem is to also provide the indexes) and in addition, it provides a new implementation with less complexity time ! Hats off for the hard work :) I will still try to fix my code but this is the perfect answer. I am editing the title for using this Q to mark other Qs in future as duplicate of this.

Haswanth Voonna · Accepted Answer · 2020-02-02 20:17:42Z

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MINUS_INFINITY -1e10

float Find_max_cross_subarray(int I[],float A[]){

    float left_sum = MINUS_INFINITY;
    float right_sum = MINUS_INFINITY;
    float sum = 0;
    int left_max,right_max,i;

    for(i=I[2];i>=I[0];i--){
        sum = sum + A[i];
        if(sum > left_sum){
        left_sum = sum;
        left_max = i;
        }
    }
     sum = 0;
    for(i=I[2]+1;i<=I[1];i++){
    sum = sum + A[i];
    if(sum > right_sum){
        right_sum = sum;
        right_max = i;
    }
}
I[0] = left_max;
I[1] = right_max;
sum = left_sum + right_sum;
return sum;
}

float Find_max_subarray(int I[],float A[]){

int sum,mid;
int left[2];
int right[2];
int cross[3];
float left_sum,right_sum,cross_sum;
if(I[0] == I[1]){
    sum = A[I[0]];
}
else {
    mid = floor((I[0]+I[1])/2);
    left[0] = I[0];
    left[1] = mid;
    right[0] = mid + 1;
    right[1] = I[1];
    cross[0] = I[0];
    cross[1] = I[1];
    cross[2] = mid;
    left_sum = Find_max_subarray(left,A);
    right_sum = Find_max_subarray(right,A);
    cross_sum = Find_max_cross_subarray(cross,A);
    if((left_sum >= right_sum)&&(left_sum >= cross_sum)){
        sum = left_sum;
        I[0] = left[0];
        I[1] = left[1];
    }
    else if((right_sum >= left_sum)&&(right_sum >= cross_sum)){
        sum = right_sum;
        I[0] = right[0];
        I[1] = right[1];
    }
    else{
        sum = cross_sum;
        I[0] = cross[0];
        I[1] = cross[1];
    }
}
return sum;
}

int main(){

int n,i;
float max_sum;
int I[2];

float A[100] = {13, -3, -25, 20, -3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; 
n = sizeof(A)/sizeof(A[0]); 
I[0] = 0;
I[1] = n-1;
max_sum = Find_max_subarray(I,A);
printf("Maximum sub array is A[%d ......%d] with sum %f",I[0],I[1],max_sum);

}

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related