最大字段和问题POJ 1050

发表于

首先，我们要了解一下最大字段和问题。什么是最大字段和？
给定一个长度为N的数列，取其中连续的长度为M(0<M<=N)的字段，使其和最大。
思想：很简单。若和值为正，就把它与当前的数相加。当这个和值为一个负数时，就把它替换。
下面上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <cstdio>
using namespace std;
int n,t,a[1001],k,tmp;
int main(){
 scanf("%d",&t);
 while(t--){
  k=-10000000,tmp=0;
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",&a[i]);
  for(int i=1;i<=n;++i){
   if(tmp>0)tmp+=a[i];
   else tmp=a[i];
			
   if(tmp>k)k=tmp;
  }
  printf("%d\n",k);
 }
 return 0;
}

理解了最大字段和，我们来做一道经典的题。
题目地址
给定一个n*n的矩阵，求一个子矩阵，使得该矩阵的元素之和最大。
我们会解一维的最大字段和，然而现在是二维的。怎么办呢？进行压缩，将二维化为一维。
先单独对每行求最大字段和（此时，子矩阵的行为1，就是最大字段和了）
然后，把第i行后的各行对应列的元素加到第i行的对应列元素，每加一行，就求一次最大字段和，这样就把子矩阵的多行压缩为一行了，一行了就是最大字段和了
上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <cstdio>
using namespace std;
int n,a[100][100],max=-1000000,tmp;
int main(){
 scanf("%d",&n);
 for(int i=0;i<n;++i){
  tmp=0;
  for(int j=0;j<n;++j){
   scanf("%d",&a[i][j]);
   if(tmp>0)tmp+=a[i][j];
   else tmp=a[i][j];
   if(tmp>max)max=tmp;
  }
 }
 for(int i=0;i<n-1;++i){
  for(int j=i+1;j<n;++j){
   tmp=0;
   for(int k=0;k<n;++k){
    a[i][k]+=a[j][k];
    if(tmp>0)tmp+=a[i][k];
    else tmp=a[i][k];
    if(tmp>max)max=tmp;
   }
  }
 }
 printf("%d",max);
}