1.I am studying “Introduction to Algorithm” by t.cormen and using Divide and Conquer technique I am

solving this.

2.My Code is not giving correct output for this problem.

3.I am having problem to understand how exactly that max_sum() function is working, it will be really

helpful if any one will explain.

here is the code:-

```
#include<stdio.h>
#define NEGINF -1000000000
#define MAX(a,b) a>b?a:b
int a[9]={-2,1,-3,4,-1,2,1,-5,4};
int max_across(int low,int mid,int high){
int i;
int leftsum,rightsum,sum,maxsum;
leftsum=NEGINF;
sum=0;
for(i=mid;i>=low;i--){
sum=sum+a[i];
if(sum>leftsum)
leftsum=sum;
}
rightsum=NEGINF;
for(i=mid+1;i<=high;i++){
sum=sum+a[i];
if(sum>rightsum)
rightsum=sum;
}
maxsum=leftsum+rightsum;
return maxsum;
```

}

```
int max_sum(int low,int high){
int left_sum,right_sum,across_sum,final_sum;
int mid=low+(high-low)/2;
if(low==high) return a[low];
left_sum=max_sum(low,mid);
right_sum=max_sum(mid+1,high);
across_sum=max_across(low,mid,high);
final_sum=MAX(MAX(left_sum,right_sum),across_sum);
return final_sum;
}
int main(){
int sum;
sum=max_sum(0,9);
printf("%d\n",sum);
return 0;
```

}