My solution to the prob using a vector<vector<int>> of my own


int Solution::solve(vector<vector > &A) {
int rows = (int)A.size()+1, cols = (int)A[0].size()+1;
int max = INT_MIN;
vector<vector> matrix(rows);
for(int i = 0; i < rows; i++){
for(int i=rows-2 ; i >= 0 ; --i){
for(int j=cols-2 ; j >= 0 ; --j){
matrix[i][j] = A[i][j];
matrix[i][j] += matrix[i+1][j] + matrix[i][j+1] - matrix[i+1][j+1];
max = matrix[i][j]>max ? matrix[i][j] : max;
return max;


Please can you explain the logic behind following quote, why you subtract (i+1, j+1)th element?


You are the real MVP.
Please, tell us how did you derive that?:scream::scream::scream:


if you observe closely the matrix[i+1][j+1] element has already been added once to matrix[i][j+1] and matrix[i+1][j] both. hence we need to subtract it once so that it is counted only one time and not two(case when we dont sub or add it) or three(in case we add it).