I'm solving the max Subarray problem with recursion but I'm getting a runtime error. I cannot figure out what the problem is. Please help me understand if you get it. Please help me with the same:
class Solution {
public:
int cross(vector<int>a, int l, int m, int h)
{
int ls=INT_MIN;
int sum=0;
for(int i=m; i>0; i--)
{
sum=sum+a[i];
if(ls<=sum)
{
ls=sum;
}
}
sum=0;
int rs=INT_MIN;
for(int i=m+1; i<h; i++)
{
sum=sum+a[i];
if(rs<=sum)
{
rs=sum;
}
}
return (ls+rs);
}
int mainfunc(vector<int>a, int l, int h)
{
if (l==h) {return a[0];}
int m=l+(h-1)/2;
int lsum=mainfunc(a, l, m);
int rsum=mainfunc(a, m+1, h);
int csum=cross(a, l, m, h);
if (lsum>=rsum && lsum>=csum){return lsum;}
else if (rsum>lsum && rsum>csum){return rsum;}
else return csum;
}
int maxSubArray(vector<int>& n) {
int sum=mainfunc(n, 0, n.size());
return sum;
}
};
Aucun commentaire:
Enregistrer un commentaire