Largest submatrix (matrix)

Description

---

The size of a known matrix is defined as the sum of all elements in the matrix. Given a matrix, your task is to find the largest Non-empty (at least 1 ( imes) 1 in size) submatrix.
For example, the following 4 ( imes) 4 matrix:

0 -2 -7 0
9  2 -6 2
-4 1 -4 1
-1 8  0 -2

Its largest submatrix is:

9 2
-4 1
-1 8

The size of this sub-matrix is 15.

Format

---

Input

An (N imes N) matrix. The first line of the input gives (N (0<N leq 100)). In the following rows, in turn(First, give the (N) integers in the first row from left to right, and then give the (N) integers in the second row from left to right...)
Given the (N imes N) integers in the matrix, the integers are separated from each other. Character separation (space or blank line). The range of integers in the known matrix are all in ([-127,127])

Output

Output the size of the largest sub-matrix.

Sample

---

Input

4
0 -2 -7  0
9  2 -6  2
-4 1 -4  1
-1 8  0 -2

Output

15

Sample Code

---

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int n,ans,a[101][101],f[101][101];

int main() {
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	cin>>n;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			cin>>a[i][j];
	ans=a[1][1];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			f[i][j]=f[i][j-1]+a[i][j];//Find the sum of the first j numbers in the i-th row.
	for(int s=1; s<=n; s++) //Find the starting column of the largest submatrix.
		for(int e=s; e<=n; e++) { //Find the ending column of the largest submatrix.
			int sum=0;
			for(int t=1; t<=n; t++) { //At this time, t represents a row, and calculate the sum of the sub-matrices row by row from column s to column e to find the largest sub-matrix.
				sum+=f[t][e]-f[t][s-1];//The sum of submatrices from column s to column e and row t,
				//cout<<"s="<<s<<";"<<"e="<<e<<";"<<"t="<<t<<";"<<"sum="<<sum<<";"<<"ans="<<ans<<endl;
				ans=max(ans,sum); //ans Find the maximum value.
				sum=max(sum,0);//If the sum of the sub-matrices is negative, it is discarded and the sum is calculated from 0.
			}
		}
	cout<<ans;
	return 0;
}