O(M*N ) DP solution


#1

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;

}