歷屆試題 最大子陣 時間限制：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; }}新聞熱點
疑難解答
