hdu 1081: to the max

题目分析:依次选择任意2,3……N-1,N行相加得到一维数mSum;

再对每次产生的一维数组mSum求最大连续子序列的和;

即把二维数组的问题转化为一维数组上的动态规划。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <stdlib.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)
int ()
{

int N;
int Matrix[100][100];
int mSum[100];
int i,j,k,p;
int MaxSum,Max,sum;
while ( scanf("%d",&N)!=EOF )
{
for ( i = 0; i < N; i++)
for ( j = 0; j < N; j++)
scanf("%d",&Matrix[i][j]);
Max = 0;
for ( k = 1; k < N; k++)
{
for ( i = 0; i + k < N;i++)
{
memset(mSum,0,sizeof(mSum));
for ( j = 0; j <= k; j++)
{
for ( p = 0; p < N;p++)
mSum[p] += Matrix[i+j][p];
}
MaxSum = 0,sum = 0;
for ( p = 0; p < N; p++)
{
sum += mSum[p];
sum = max(sum,mSum[p]);
MaxSum = max(MaxSum,sum);
}
if (MaxSum > Max)
Max = MaxSum;
}
}
printf("%dn",Max);
}
return 0;
}