NYOJ 104最大和
3404 ワード
最大合計
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
5
説明
整数からなる2次元行列(r*c)が与えられ、このサブ行列内のすべての要素の和が最大になるように、そのサブ行列を見つける必要があり、このサブ行列を最大サブ行列と呼ぶ.例:0-2-7 0 9 2-6 2-4 1-4 0-2
9 2-4 1-18要素の合計は15です.
入力
1行目には、n組のテストデータがあることを示す整数n(0各テストデータのセット:
第1行には2つの整数r,c(0その後、r行があり、各行にc個の整数がある.
しゅつりょく
出力マトリクスの最大サブマトリクスの要素の和.
サンプル入力
サンプル出力
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
5
説明
整数からなる2次元行列(r*c)が与えられ、このサブ行列内のすべての要素の和が最大になるように、そのサブ行列を見つける必要があり、このサブ行列を最大サブ行列と呼ぶ.例:0-2-7 0 9 2-6 2-4 1-4 0-2
9 2-4 1-18要素の合計は15です.
入力
1行目には、n組のテストデータがあることを示す整数n(0
第1行には2つの整数r,c(0
しゅつりょく
出力マトリクスの最大サブマトリクスの要素の和.
サンプル入力
1
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
サンプル出力
15
// , ,
//ループが すぎるかもしれません.sum の の くは を り してタイムアウトしました.タイムアウトコード:#include<stdio.h>
#define MAX 105
int a[MAX][MAX];
int sum(int n,int m){
int sum=0;
int max=-100;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
sum+=a[i][j];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
}
return max;
}
void print(int n,int m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
printf("%d ",sum(i,j));
printf("
");
}
}
int main(){
int N,n,m;
scanf("%d",&N);
while(n--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
int max=-100;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
if(sum(i,j)>max)
max=sum(i,j);
}
//print(n,m);
printf("%d
",max);
}
}
#include<stdio.h>
#define MAX 105
int a[MAX][MAX];
int sum(int n,int m){
int sum=0;
int max=-100;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
sum+=a[i][j];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
}
return max;
}
void print(int n,int m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
printf("%d ",sum(i,j));
printf("
");
}
}
int main(){
int N,n,m;
scanf("%d",&N);
while(n--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
int max=-100;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
if(sum(i,j)>max)
max=sum(i,j);
}
//print(n,m);
printf("%d
",max);
}
}
// , a[i][j]+=a[i-1][j] ,AC :
#include<stdio.h>
#include<string.h>
#define MAX 105
int a[MAX][MAX];
int N,n,m;
/*void print(int n,int m){
for(int i=0;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",a[i][j]);
printf("
");
}
}*/
int main(){
scanf("%d",&N);
while(N--){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
a[i][j]+=a[i-1][j];
}
int max=a[1][1];
int sum=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
sum=0;
for(int k=1;k<=m;k++){
if(sum>=0)sum+=a[j][k]-a[i-1][k];
if(sum<0)sum=a[j][k]-a[i-1][k];
if(sum>max) max=sum;//
// printf("*************%d
",max);
}
}
}
//print(n,m);
printf("%d
",max);
}
}