It is very simple to understand o(n^2)


#1

int Solution::solve(vector<vector > &A, int B) {
int n=A.size();
vector<vector >v(n+1,vector(n+1,0));
for(int i=0;i<n;i++){
for(int j=1;j<n;j++)
A[i][j]+=A[i][j-1];
}
for(int i=0;i<n;i++){
for(int j=1;j<n;j++)
A[j][i]+=A[j-1][i];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
v[i+1][j+1]+=A[i][j];
}
int M=INT_MIN;
for(int i=B;i<n+1;i++){
for(int j=B;j<n+1;j++){
int u=v[i-B][j]-v[i-B][j-B];
u+=v[i][j-B]-v[i-B][j-B];
u+=v[i-B][j-B];
M=max(M,v[i][j]-u);
}
}
return M;
}