TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

87.0% (167/192)

Submission's AC Ratio

34.9% (275/788)

Tags

Description

在數學中,某個數列的子數列是從最初數列通過去除某些元素,但不破壞餘下元素的相對位置(在前或在後)而形成的新數列。例如,1,3,4即是1,2,3,4,5 的一個子數列。

最大連續和問題是一個子數列相關的經典問題,目標是在數列中找到一個連續的子數列,使該子數列的和最大。例如,對一個數列2,1,3,4,1,2,1,5,4,其連續子數列中和最大的是4,1,2,1 其和為6

在某個小島舉行的ACM-ICPC 區域賽中,常常會有許多經典問題。身為一個專業的競賽選手,艾迪十分熟練各種經典題的做法,因此也常常在該賽區神速般獲得各種Accepted

但就在這次競賽中,艾迪稍微遇到了小波折。這次艾迪遇到的問題已經不是經典題了,而是只有一字之差的最大不連續和問題!即要在數列中找到一個不連續的子數列,使得該子數列的總和最大。

例如,對一個數列1,1,1,1,3,10,其不連續的子數列中和最大的是1,1,1,10 其和為13

由於艾迪已經驚慌失措了,你能夠幫助他解決這個問題嗎?

Input Format

測試資料第一行有一個數字N,表示數列的⻑度。
第二行有N 個整數A1,A2,,AN,表示數列。

  • 3N106
  • |Ai|109

Output Format

輸出一個數字於一行,表示最大不連續和的值。

Sample Input 1

3
-1 -2 -3

Sample Output 1

-4

Sample Input 2

6
1 1 1 -1 -3 10

Sample Output 2

13

Sample Input 3

10
9 4 3 8 1 5 10 7 2 6

Sample Output 3

54

Hints

Problem Source

2017 NPSC高中組決賽

Subtasks

No. Testdata Range Score
1 0~65 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1
37 1000 262144 262144 1
38 1000 262144 262144 1
39 1000 262144 262144 1
40 1000 262144 262144 1
41 1000 262144 262144 1
42 1000 262144 262144 1
43 1000 262144 262144 1
44 1000 262144 262144 1
45 1000 262144 262144 1
46 1000 262144 262144 1
47 1000 262144 262144 1
48 1000 262144 262144 1
49 1000 262144 262144 1
50 1000 262144 262144 1
51 1000 262144 262144 1
52 1000 262144 262144 1
53 1000 262144 262144 1
54 1000 262144 262144 1
55 1000 262144 262144 1
56 1000 262144 262144 1
57 1000 262144 262144 1
58 1000 262144 262144 1
59 1000 262144 262144 1
60 1000 262144 262144 1
61 1000 262144 262144 1
62 1000 262144 262144 1
63 1000 262144 262144 1
64 1000 262144 262144 1
65 1000 262144 262144 1