Maximum subarray probelm

general
,
1

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;

}

2

I think you have missed something in max_across function…

leftsum=NEGINF;

sum=0;

for(i=mid;i>=low;i--){

 sum=sum+a[i];

 if(sum>leftsum){

  leftsum=sum;

  lefti=i;

 }

}

In this if statement you have defined block… but in rightsum part, there is no such block in if statement

rightsum=NEGINF;

for(i=mid+1;i<=high;i++)
{

sum=sum+a[i];

if(sum>rightsum)

rightsum=sum;

righti=i;

}

The problem with your wrong answer is this…

From your code I guess you want to find the maximum sum sub-sequence array through the use of divide and conquer technique???

If this is the case then your implementation is incorrect…

3

I read the pseudo code from Introduction to Algorithm from the divide and conquer chapter.

4

max_sum() function works by initially calculating the maximum subarray in left half, right half, cross-over subarray and then finds the maximum.

For instance in the left half, when the line left_sum = max_sum(low, mid) {initially low = 0, mid = 4} is executed, repeated recursive calls are made till it narrows down to one element(base case){at this point low = 0, mid = 0} and then right_sum is the next element{high = 1} and the sum of these two elements {element at the zeroth index and first index} is calculated by max_across(low, mid, high) {low = 0, mid = 0, high = 1}. Now since line of control has to go back to the function call statement, in this process the sum of the rest of the elements in the left half of the array is calculated and its maximum is stored in left_sum.

Then the next line is executed and right_sum is calculated in a similar manner as above.

Finally across_sum calculates the maximum subarray that crosses over ie the indices of the elements is such that low <= i <= high (where ‘i’ is the index of an element).

I will leave it to you to figure out what will be the values of low, mid and high in each recursive call as this will help you understand the working of max_sum() very clearly. Hope this helps!

5

thanks for the reply,but I have understood this from the pseudo code and thats how I code but when I came to paper and pen, I could not figure out the working, it was like solving big puzzle and I was totally confused and messed up. That’s why I am unable to figure out why that code is giving wrong answer.

6

I edited code and removed that part.

7

I have formatted your program and print some intermediate results http://ideone.com/PHpxdV

8

#include
using namespace std;

int main(){
long long N,max;
long long * A;
cin>>N;
while(N!=0){
A=new long long[N];
max=-1000000000;
for(int i=0;i<N;i++){
cin>>A[i];
if(A[i]>max)max=A[i];
}
cout<<max<<endl;
delete[] A;
cin>>N;
}
return 0;
}

9

after you calculated the maximum left-sum you need to initialise sum to 0 again, and then compute right sum.

1 Like
10

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;

}
sum=0;//sum already contains previous value of leftsum
rightsum=NEGINF;
for(i=mid+1;i<=high;i++){
sum=sum+a[i];
if(sum>rightsum)
rightsum=sum;
}
maxsum=leftsum+rightsum;
return maxsum;
}