题意：给出N*N的矩阵，求一个子矩阵使得子矩阵中元素和最大
分析：
必备知识：求一组数的最大连续和
int a[N];
int sum = ,maxn = -INF;
for(int i = ; i <= n; i++)
{
if(sum + a[i] > a[i])
sum += a[i];
else
sum = a[i];
maxn = max(sum, maxn);
}
一维数组最大连续和
假设要求的子矩阵位于 r 行到 i 行，c 列到 j 列之间怎么找出这个值呢？
方法：可以讲矩阵从 r 行 到 i 行 之间按照列求和放到一个数组中，colsum[y] 表示 y 列所有元素的和，所以对这个colsum[] 来求最大连续和 就得出解来
但是不知道 最大子矩阵 是位于那两个行之间， 需要两重循环枚举r 行 到 i 行
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = ;
const int INF = 0x3f3f3f3f;
int matrix[Max][Max];
int colsum[Max],n,maxn;
int maxcolsum()
{
int ans = , colmax = -INF;
for(int i = ; i <= n; i++)
{
if(colsum[i] + ans > colsum[i])
ans += colsum[i];
else
ans = colsum[i];
if(colmax < ans)
colmax = ans;
}
return colmax;
}
int maxMatrix()
{
for(int i = ; i <= n; i++)
{
memset(colsum, , sizeof(colsum));
for(int j = i; j <= n; j++)
{
for(int k = ; k <= n; k++)
colsum[k] += matrix[j][k]; //求 从 i 行到 j 行所有的列元素的和
int ans = maxcolsum(); // 对列元素和 求 最大连续和
if(maxn < ans)
maxn = ans;
}
}
return maxn;
}
int main()
{ while (scanf("%d", &n) != EOF)
{
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
scanf("%d", &matrix[i][j]);
maxn = -INF;
printf("%d\n",maxMatrix());
}
return ;
}