注：该程序本人已提交网站并通过，希望提供一定帮助。
原题目：最大子矩阵
【题目描述】1224
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×1)子矩阵。
【输入】
输入是一个N×N的矩阵。输入的第一行给出N(0<N<=100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
【输出】
输出最大子矩阵的大小。
【输入样例】
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
【输出样例】
15
理解： 本题考查二维数组的使用与变化和少量的算法应用，逻辑较为简单，其实就是一道关于矩阵的变化的题目。题目说明中指明要“矩阵”，所以我们就要保证我们在算法计算中每一步的本质性图形是个矩形（也就是长方形或正方形）。而为了尽量的减少时间复杂度，我们用两个数组。加之由递归式的思维得出的关于一维直线式求最大和需要2个循环的结论看出，我们做二维矩阵是可以用三循环做出的。（这里的的所谓“几循环”是指程序中维数最多的循环的维数，列如有一个程序，它有3个一循环和2个2循环，一个3循环，还有1个4循环，那么它就会被称作四循环程序）我们可以用一个变量ans每次算出这个子矩阵的总和，再依次作比较找出最大的即可。
应用： 防止ans为0以下，ans大于nmax时赋值，其他按普通矩阵程序做就行了。思考时要注意二维的情况不好像，先从一维的判断最长线段开始推。
完整无标记程序（无批注）：
#include<iostream>
using namespace std;
long long a[1001][1001],b[1001][1001];
int main()
{
int n,main=0,ans,nmax=-300;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
main=main+a[i][j];
b[i][j]=main;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
ans=0;
for(int f=1;f<=n;f++)
{
ans=ans+b[f][j]-b[f][i-1];
if(ans>nmax) nmax=ans;
if(ans<0) ans=0;
}
} cout<<nmax;
return 0;
}
程序注解（含批注）：
#include<iostream> //内容中含有输入(cin)和输出(cout)类的c++语句，因此要调用iostream库
using namespace std; //保证程序的正常运行
int a[1001][1001],b[1001][1001]; //定义数组a和b，a数组用于输入时的单个数存储，范围不太大，最多也只有127，（题目原句："已知矩阵中整数的范围都在[−127,127]。" int数据类型是可以存储0和负数的）所以用int。b数组用于标记和计算前缀和
int main() //main是主要的意思，意为主程序部分
{
int n,main=0,ans,nmax=-300; //定义边长n，用于算当前总和的mian，用于计算总量的ans，nmax可以和ans进行比较，从而求出最大的一个子矩阵的和，然后输出它
cin>>n; //输入边长n
for(int i=1;i<=n;i++) //双循环，一个i，一个j，输入整个矩阵
for(int j=1;j<=n;j++) //双循环，一个i，一个j，输入整个矩阵
{
cin>>a[i][j]; //输出当前这个位置上的数，存入a数组，i为纵坐标，j为横坐标
main=main+a[i][j]; //main每次都增加，表示当前的总和，但它还不能直接计算前缀和，因此后面得再开一个三循环来分离每部分，算前缀和
b[i][j]=main; //当前总和存入b数组
}
for(int i=1;i<=n;i++) //从左上角开始，每行每列的分离出矩形的一部分，计算比较前缀和
for(int j=1;j<=n;j++) //从左上角开始，每行每列的分离出矩形的一部分，计算比较前缀和
{
ans=0; //每次计算比较前都要先清零ans，要不然上次的数据就还在里面，影响结果
for(int f=1;f<=n;f++) //不能重复，因此用f。这个循环的作用是保证分离出来的是矩形
{
ans=ans+b[f][j]-b[f][i-1]; //这个就是求前缀和的简单算法，我们由思考得出结论，举例子，从10到2的这部分的总和怎么计算开始思考，得出结论，算法是从10到1这部分的总和减去从0到的1的总和，代数式化后就变成了上面这句“ans=ans+b[f][j]-b[f][i-1];”
if(ans>nmax) nmax=ans; //如果当前的和比之前记录的最大子矩阵和大的话，就重新赋值最大，代表ans刷新了nmax的最大记录，因此现在的最大记录就是ans。
if(ans<0) ans=0; //如果ans是个负数，就把它归零处理
}
} cout<<nmax; //输出
return 0; //程序终止
}