O(n^3) as we do in finding submatrix with zero sum


#1

int Solution::solve(vector<vector > &A)
{
int max=A[0][0];
int m=A.size();
int n=A[0].size();
int j;
int sum;
int minel;
int total=0;
int maxel;
vectorhelp;

int i=n-1;//here taking only last column is enoungh as column wise strength increases,this reduces to 

o(n^3)

    for(int j=i;j>=0;j--)
    {
        for(int p=0;p<m;p++)
        {
            sum=0;
            for(int k=i;k>=j;k--)
            {
                sum=sum+A[p][k];
            }
            help.push_back(sum);
        }
       
        minel=0;
        maxel=help[0];
        for(int q=0;q<help.size();q++)
        {
            total+=help[q];
            if(total-minel>maxel)
            {
                maxel=total-minel;
            }
            if(minel>total)
            {
                minel=total;
            }
        }
        if(maxel>max)
        {
            max=maxel;
        }
        total=0;
        help.clear();
    }
    
return max;

}


#2

Comment body goes here.int Solution::solve(vector<vector > &A) {

int dp[A.size()+2][A[0].size()+2]={0};
dp[A.size()-1][A[0].size()-1]=A[A.size()-1][A[0].size()-1];

int maxi=INT_MIN;
maxi=max(dp[A.size()-1][A[0].size()-1],maxi);

if(A.size()==1 &&A[0].size()==1) return A[0][0];
for(int i=A.size()-2;i>=0;i--){
    
    dp[i][A[0].size()-1]=dp[i+1][A[0].size()-1]+A[i][A[0].size()-1];
    maxi=max(maxi,dp[i][A[0].size()-1]);
    
}
for(int i=A[0].size()-2;i>=0;i--){
    
    dp[A.size()-1][i]=dp[A.size()-1][i+1]+A[A.size()-1][i];
    maxi=max(maxi,dp[A.size()-1][i]);
}
for(int i=A.size()-2;i>=0;i--){
     for(int j=A[i].size()-2;j>=0;j--){
        dp[i][j]=dp[i][j+1]+A[i][j]+dp[i+1][j]-dp[i+1][j+1];    

         maxi=max(maxi,dp[i][j]);
       
     }   

}

return maxi;

}