poj2593

60 阅读 0 评论 40 点赞

我是靠谱客的博主傲娇冬瓜，最近开发中收集的这篇文章主要介绍poj2593，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Max Sequence

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 13533		Accepted: 5654

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).

You should output S.

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

Source

POJ Monthly--2005.08.28,Li Haoyuan

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int dp1[100010],dp2[100010];
 8 int a[100010];
 9 int n;
10 int maxD;
11 
12 int main()
13 {
14 
15     while(scanf("%d",&n)!=EOF && n)
16     {
17         memset(dp1,0,sizeof(dp1));
18         memset(dp2,0,sizeof(dp2));
19         for(int i=1; i<=n; i++)
20         {
21             scanf("%d",&a[i]);
22         }
23         //dp for 最大子序列和
24         dp1[0]=-10000000;
25         for(int i=1; i<=n; i++)
26         {
27             if(dp1[i-1]<0)
28                 dp1[i]=a[i];
29             else
30                 dp1[i]=dp1[i-1]+a[i];
31         }
32         for(int i=1; i<=n; i++)
33         {
34             if(dp1[i-1]>dp1[i])
35             {
36                 dp1[i]=dp1[i-1];
37             }
38         }
39 
40         //reverse dp
41         dp2[n+1]=-10000000;
42         for(int i=n; i>=1; i--)
43         {
44             if(dp2[i+1]<0)
45                 dp2[i]=a[i];
46             else
47                 dp2[i]=dp2[i+1]+a[i];
48         }
49         for(int i=n; i>=1; i--)
50         {
51             if(dp2[i+1]>dp2[i])
52                 dp2[i]=dp2[i+1];
53         }
54 
55         //cal
56         maxD=-10000000;
57         for(int i=1; i<=n-1; i++)
58         {
59             if(dp1[i]+dp2[i+1] > maxD)
60                 maxD=dp1[i]+dp2[i+1];
61         }
62 
63         printf("%dn",maxD);
64     }
65     return 0;
66 }