My code finds the maximum subarray sum and the starting and ending 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 sA=-1,eA=-1,sB=-1,eB=-1,sC=-1,eC=-1;
int a=MaxSubArray(arr,l,mid,sA,eA);
int b=MaxSubArray(arr,mid+1,r,sB,eB);
int c=MaxAcrossSubArray(arr,l,mid,r,sC,eC);
int Maximum=Max(a,b,c);
if(Maximum==a)
{
Start=sA;
End=eA;
return a;
}
else if(Maximum==b)
{
Start=sB;
End=eB;
return b;
}
else
{
Start=sC;
End=eC;
return c;
}
}
}
}
int main()
{
int arr[9]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
int Start=-1;
int End=-1;
cout<<MaxSubArray(arr,0,8,Start,End)<<"\n";
cout<<Start<<"\n";
cout<<End<<"\n";
for(int i=Start;i<=End;++i)
{
cout<<arr[i]<<"\t";
}
cout<<"\n";
return 0;
}
Is there any way to optimize this?
#include
lines - if you edit to add them, we'll have a complete program that we could compile and run. \$\endgroup\$ – Toby Speight Sep 23 '19 at 9:25