TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

86.2% (25/29)

Submission's AC Ratio

27.8% (35/126)

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$ 個整數$A_1, A_2, \ldots, A_N$,表示數列。

  • $3 \leq N \leq 10^ 6$
  • $\lvert A_i \rvert \leq 10^ 9$

Output Format

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

Sample Input

Sample Input #1
3
-1 -2 -3

Sample Input #2
6
1 1 1 -1 -3 10

Sample Input #3
10
9 4 3 8 1 5 10 7 2 6

Sample Output

Sample Output #1
-4

Sample Output #2
13

Sample Output #3
54

Hints

Problem Source

2017 NPSC高中組決賽

Subtasks

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