dimanche 29 novembre 2020

What is wrong with my recursion? Max Subarray Problem

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