题目描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。
输入
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。
再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。
已知矩阵中整数的范围都在[-127, 127]。
输出
测试数据可能有多组，对于每组测试数据，输出最大子矩阵的大小。
样例输入
1
27
3
-40 29 -16
38 18 22
24 -35 5
样例输出
27
78分析：求一维数组的最大子序列和比较容易。对于一个二维矩阵，可以把它看做是由若干个列向量组成的，这样二维矩阵的最大子矩阵大小，也可以变成求一个一维矩阵的最大子序列和，只是这个一维矩阵中的元素全部都是列向量。
-
枚举所有可能的上边界
i和下边界j，即从第i行到第j行之间形成的矩阵。 -
将第
i到j行之间的每一列的数加起来，得到一维数组c[k]：表示第k列在这些行中元素的和。 -
对于每个
c[]，使用 Kadane 算法 计算一维最大子段和（等价于在这个子矩阵中找最大矩形块）。 -
在所有上下边界中，记录出现的最大值。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0x3fffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n;while(~scanf("%d",&n)){int ans=-1*INF;int mtrix[n+5][n+5];for(int i=0;i<n;++i)for(int j=0;j<n;++j)scanf("%d",&mtrix[i][j]);for(int i=0;i<n;++i){int cnt[n+5]={0};for(int j=i;j<n;++j){for(int l=0;l<n;++l)cnt[l]+=mtrix[j][l];int temp=0,maxn=cnt[0];for(int k=0;k<n;++k){if(temp+cnt[k]>=0)temp=temp+cnt[k],maxn=max(maxn,temp);else temp=0;}
// db2(temp,maxn);ans=max(ans,maxn);}}printf("%d\n",ans);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
