# Maximum Sum Square SubMatrix

Problem Description

Given a 2D integer matrix A of size `N x N` find a `B x B` submatrix where B<= N and B>= 1, such that sum of all the elements in submatrix is maximum.

Problem Constraints

1 <= N <= 103.

1 <= B <= N

-102 <= A[i][j] <= 102.

Input Format

First arguement is an 2D integer matrix A.

Second argument is an integer B.

Output Format

Return a single integer denoting the maximum sum of submatrix of size `B x B`.

Example Input

Input 1:

``` A = [
[1, 1, 1, 1, 1]
[2, 2, 2, 2, 2]
[3, 8, 6, 7, 3]
[4, 4, 4, 4, 4]
[5, 5, 5, 5, 5]
]
B = 3
```

Input 2:

``` A = [
[2, 2]
[2, 2]
]
B = 2
```

Example Output

Output 1:

``` 48
```

Output 2:

``` 8
```

Example Explanation

Explanation 1:

```    Maximum sum 3 x 3 matrix is
8 6 7
4 4 4
5 5 5
Sum = 48
```

Explanation 2:

``` Maximum sum 2 x 2 matrix is
2 2
2 2
Sum = 8```

`Solution - Learn about Prefix sum in 2D Matrix`
`int Solution::solve(vector<vector<int> > &v, int k) {    int ans=INT_MIN,n=v.size();    vector<vector<int>>sum(v.size(),vector<int>(v.size(),0));    sum=v;    for(int j=1; j<n; j++)sum[j]=sum[j-1]+v[j];    for(int i=1; i<n; i++)sum[i]=sum[i-1]+v[i];        for(int i=1; i<n; i++){        for(int j=1; j<n; j++)        sum[i][j]=v[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];    }    for (int i = k - 1; i < n; i++)    {        for (int j = k - 1; j < n; j++)        {             int total = sum[i][j];            if (i - k >= 0) {                total = total - sum[i - k][j];            }             if (j - k >= 0) {                total = total - sum[i][j - k];            }             if (i - k >= 0 && j - k >= 0) {                total = total + sum[i - k][j - k];            }             ans=max(ans,total);        }    }    return ans;        }`