【題目描述】

已知矩陣的大小定義為矩陣中所有元素的和。給定一個(gè)矩陣，你的任務(wù)是找到最大的非空(大小至少是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

這個(gè)子矩陣的大小是15。

【輸入】

輸入是一個(gè)N×N的矩陣。輸入的第一行給出N(0<N≤100)。再后面的若干行中，依次(首先從左到右給出第一行的N個(gè)整數(shù)，再?gòu)淖蟮接医o出第二行的N個(gè)整數(shù)……)給出矩陣中的N2個(gè)整數(shù)，整數(shù)之間由空白字符分隔(空格或者空行)。已知矩陣中整數(shù)的范圍都在[?127,127]。

【輸出】

輸出最大子矩陣的大小。

【輸入樣例】

4
0 -2 -7? 0
9? 2 -6? 2
-4? 1 -4? 1
-1? 8? 0 -2

【輸出樣例】

15

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int a[N][N],f[N]; int maxArray(int t[],int n) {int sum=0,maxx=-INF;for(int i=1;i<=n;i++){if(sum>0)sum+=t[i];elsesum=t[i];if(sum>maxx)maxx=sum;}return maxx; } int main() {int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];int maxx=-INF;for(int i=1;i<=n;i++){memset(f,0,sizeof(f));for(int j=i;j<=n;j++){for(int k=1;k<=n;k++)f[k]+=a[j][k];int temp=maxArray(f,n);if(temp>maxx)maxx=temp;}}cout<<maxx<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的最大子矩阵（信息学奥赛一本通-T1282）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。