poj2593与poj2479

poj-2479http://acm.pku.edu.cn/JudgeOnline/problem?id&＃61;2479

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long s1[50001],s2[50001],max;
int a[50001],n,t;
int main(){
int i,j,i1;
scanf("%d",&t);
for(i1&＃61;1;i1<&＃61;t;i1&＃43;&＃43;)
{
s1[0]&＃61;0;s2[0]&＃61;0;
scanf("%d",&n);
for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
scanf("%d",&a[i]);

s1[1]&＃61;a[1];max&＃61;a[1];
for(i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
if(s1[i-1]&＃43;a[i]<a[i])s1[i]&＃61;a[i];
else s1[i]&＃61;s1[i-1]&＃43;a[i];

for(i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
{
if(max>s1[i])s1[i]&＃61;max;
max&＃61;s1[i];
}

s2[n]&＃61;a[n];
max&＃61;a[n];
for(i&＃61;n-1;i>&＃61;1;i--)
if(s2[i&＃43;1]&＃43;a[i]<a[i])s2[i]&＃61;a[i];
else s2[i]&＃61;s2[i&＃43;1]&＃43;a[i];


for(i&＃61;n-1;i>&＃61;1;i--)
{
if(max>s2[i])s2[i]&＃61;max;
max&＃61;s2[i];
}

max&＃61;s1[1]&＃43;s2[2];
for(i&＃61;1;i<&＃61;n-1;i&＃43;&＃43;)
if(max<(s1[i]&＃43;s2[i&＃43;1]))
max&＃61;s1[i]&＃43;s2[i&＃43;1];
printf("%ld\n",max);

}
return 0;
}

s1[]表示从1到i的最大子序列和中的最大值&＃xff0c;s2[i]表示从n到i的最大子序列和中的最大值。最初时s1[i ]表示从1开

到i的最大子序列和,s2[ ]表示从n开始向前到i的最大子序列和。然后再用max对两数组进行了处理。最终所要的答案

是s1[i]&＃43;s2[i&＃43;1]中最大的一个。此题同poj-2593&＃xff0c;是hdu-1003的强化版.

poj-2593http://acm.pku.edu.cn/JudgeOnline/problem?id&＃61;2593

代码

1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4  long s1[100500],s2[100500],max;
5  int a[100500],n;
6  int main(){
7 int i,j;
8 scanf("%d",&n);
9
10 while(n!&＃61;0)
11 {
12 for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
13 scanf("%d",&a[i]);
14 s1[1]&＃61;a[1];
15 max&＃61;a[1];
16 for(i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
17 if(s1[i-1]&＃43;a[i]<a[i])s1[i]&＃61;a[i];
18 else s1[i]&＃61;s1[i-1]&＃43;a[i];
19
20 for(i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
21 {
22 if(max>s1[i])s1[i]&＃61;max;
23 max&＃61;s1[i];
24 }
25
26 s2[n]&＃61;a[n];
27 max&＃61;a[n];
28
29 for(i&＃61;n-1;i>&＃61;1;i--)
30 if(s2[i&＃43;1]&＃43;a[i]<a[i])s2[i]&＃61;a[i];
31 else s2[i]&＃61;s2[i&＃43;1]&＃43;a[i];
32
33  for(i&＃61;n-1;i>&＃61;1;i--)
34 {
35  if(max>s2[i])s2[i]&＃61;max;
36 max&＃61;s2[i];
37 }
38
39 max&＃61;s1[1]&＃43;s2[2];
40 for(i&＃61;2;i<&＃61;n-1;i&＃43;&＃43;)
41 if(max<(s1[i]&＃43;s2[i&＃43;1]))
42 max&＃61;s1[i]&＃43;s2[i&＃43;1];
43
44 printf("%ld\n",max);
45 scanf("%d",&n);
46 }
47 return 0;
48 }