历届试题 最大子阵 时间限制：1.0s 内存限制：256.0MB 提交此题 问题描述 给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。
其中，A的子矩阵指在A中行和列均连续的一块。 输入格式 输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。 接下来n行，每行m个整数，表示矩阵A。 输出格式 输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 样例输入 3 3 -1 -4 3 3 4 -1 -5 -2 8 样例输出 10 样例说明 取最后一列，和为10。 数据规模和约定 对于50%的数据，1<=n, m<=50； 对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。
最大子矩阵的做法是将矩阵变化， 就是把最大子矩阵变成最大连续子序列和，把二维变成一维。 如下图 奖每竖行的和记录，形成一个新的矩阵， 这样只需要枚举所有的i，j，求i到j的连续和最大的数。 最后找到的就是一个矩阵
3 3-1 -4 33 4 -1-5 -2 8-1 -4 32 0 2-3 -2 10#include <iostream>#include <string>#include <cstring>#include <stdio.h>#include <cmath>using namespace std;long long d[600][600],p[600][600];int main(){ int n,m; while(cin>>n>>m) { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>d[i][j]; } }//cout<<endl; for(j=1;j<=m;j++) { long long x=0; for(i=1;i<=n;i++) { x+=d[i][j]; p[i][j]=x; } } /* for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<p[i][j]<<' '; } cout<<endl; } */ int maxsum=-10000000; int x,y,z; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { int thissum=0; for(int k=1;k<=m;k++) { thissum+=p[j][k]-p[i-1][k]; if(thissum>maxsum) { x=i;y=j;z=k; maxsum=thissum; } if(thissum<0) thissum=0; } } } // cout<<x<< ' '<<y<<' '<<z<<endl; cout<<maxsum<<endl; }}新闻热点
疑难解答
