MaximumSubArray.cpp

#include <iostream>
using namespace std;

int count;
struct SubArray{
    int low ,high;
    double sum;
    
    SubArray()
    {}
    
    SubArray(int l, int h, double s){
        low = l;
        high = h;
        sum =s;
    }
};

SubArray MaximumCrossArray(double a[],int low,int mid,int high){
    double leftsum = -9999;
    double sum = 0;
    int i;
    for(i=mid;i>-low;i--){
        sum = sum + a[i];
        if(sum>leftsum)
            leftsum = sum;
    }
    double maxleft = i;
    double rightsum = -9999;
    sum = 0;
    int j ;
    for( j = mid+1;j<=high;j++){
        sum = sum+a[j];
        if(sum>rightsum)
            rightsum = sum;
    }
    double maxright = j;
    return SubArray(maxleft,maxright,leftsum+rightsum);
}

SubArray MaximumSubArray(double a[],int low ,int high){
    SubArray left,right,cross;
    if(low == high){
        return SubArray(low,high,a[low]);
    }
    count++;
    int mid = (low+high)/2;
    left = MaximumSubArray(a,low,mid);
    right = MaximumSubArray(a,mid+1,high);
    cross = MaximumCrossArray(a,low,mid,high);
    
    if(left.sum>=right.sum && left.sum>=cross.sum)
        return SubArray(left.low,left.high,left.sum);
    else if(right.sum>=left.sum && right.sum>=cross.sum)
        return SubArray(right.low,right.high,right.sum);
    else
        return SubArray(cross.low,cross.high,cross.sum);
}

int main(){
    double arr[] = { 2, 3, 4,5,7,8,9,10,12,1,4,1,5,1,6,1,7 };
    double n = sizeof(arr) / sizeof(arr[0]);
    SubArray Max;
    Max = MaximumSubArray(arr,0,n-1);
    for(int i = Max.low ; i<=Max.high;i++){
        cout<<i<<"\t"<<arr[i]<<endl;
    }
    cout<<"Count: "<<count<<endl;

}