Finding the maximum subarray using recursion

One way to do is using two loops which gives us the time complexity O(n²), but by using divide and conquer approach we can solve it in O(nLogn) time.
Algorithm:

Divide the given array in two subarrays, now the contiguous subarray must lie in exactly one of the following places:

• Entirely in first subarray.
• Entirely in second subarray.
• Crossing the midpoint of both the subarrays.

Now, first two sub problems are similar instances of the problem of finding the maximum subarray and hence can be solved recursively. 

So, we need to find a maximum subarray crossing the midpoint which can be done in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.

Here's the code:

#include<stdio.h>
struct tuple{
    int left;
    int right;
    int sum;
};

struct tuple find_max_cross_subArray(int *a,int low,int mid,int high){
    int i,j,sum=0,maxleft,maxright;
struct tuple res;
    int leftsum=-2147483648; 
    int rightsum=-2147483648;
    for(i=mid;i>=low;i--){
        sum+=a[i];               
        if(sum>leftsum){
             leftsum=sum;
             maxleft=i;
        }   
    }
    sum=0;
    for(j=mid+1;j<=high;j++){
        sum+=a[j];
        if(sum>rightsum){
             rightsum=sum;
             maxright=j;
        }                     
    }
    res.left=maxleft;
    res.right=maxright;
    res.sum=leftsum+rightsum;
    return res;
}

struct tuple find_max_subArray(int *a, int low, int high){
    struct tuple res,leftres,rightres,crossres;
    int mid;
    
    if(low==high){
        res.left=low;
        res.right=high;
        res.sum=a[low];
        return res;
    }
    else{
        mid=(low+high)/2;
        leftres=find_max_subArray(a,low,mid);
        rightres=find_max_subArray(a,mid+1,high);
        crossres=find_max_cross_subArray(a,low,mid,high);
        if(leftres.sum>=rightres.sum && leftres.sum>=crossres.sum)
            return leftres;
        else if(rightres.sum>=leftres.sum && rightres.sum>=crossres.sum)
            return rightres;
        else
            return crossres;
    }
}

int main(){
int a[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
int n = sizeof(a)/sizeof(a[0]);
struct tuple result;
result=find_max_subArray(a,0,n-1);
printf("Maximum contiguous subarray lies from: %d to %d\nThe maximum sum is :%d",result.left+1,result.right+1,result.sum);
return 0;

}

There is an even better algorithm for this problem, which is Kadane's algorithm which takes O(n) time. Click here to see Kadane's algorithm.