My code above about find maximum subarray sum and finding start index,end index of that subarray.
int Max(int a,int b){return (a>b)?a:b;}
int Max(int a,int b,int c){return Max(Max(a,b),c);}
int MaxAcrossSubArray(int arr[],int l,int m,int r,int &Start,int &End)
{
Start=m;//initialize start index
int sum=arr[m];
int sum_l=arr[m];
for(int i=m-1;i>=l;--i)//include mid(---------|)
{
sum+=arr[i];
if(sum>sum_l)
{
Start=i;
sum_l=sum;
}
}
End=m+1;//initialize end index
sum=arr[m+1];
int sum_r=arr[m+1];
for(int i=m+2;i<=r;++i)//include mid(|-----------------)
{
sum+=arr[i];
if(sum>sum_r){
End=i;
sum_r=sum;
}
}
return sum_l+sum_r;//(-----------|---------------------)
}
int MaxSubArray(int arr[],int l,int r,int &Start,int &End)
{
if(l==r)
{
Start=l;
End=r;
return arr[l];
}
else
{
int mid=(l+r)/2;
int a=MaxSubArray(arr,l,mid,Start,End);
int b=MaxSubArray(arr,mid+1,r,Start,End);
int c=MaxAcrossSubArray(arr,l,mid,r,Start,End);
int Maximum=Max(a,b,c);
if(Maximum==a)
return MaxSubArray(arr,l,mid,Start,End);
else if(Maximum==b)
return MaxSubArray(arr,mid+1,r,Start,End);
else
return MaxAcrossSubArray(arr,l,mid,r,Start,End);
}
}
My algorithm run good for any case but i still need you guys help me to improve my algorithm for better.Is there any way to make it better?
a = maxSub(startA, endA); if(max == a) { start = startA; end = endA; return a; }
– Aconcagua Sep 22 at 17:07