TopCoder

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

User's AC Ratio

89.1% (90/101)

Submission's AC Ratio

32.5% (121/372)

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

No. Testdata Range Score
1 0~65 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (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