2048 . G.最大不連續和問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

86.8% (165/190)

Submission's AC Ratio

34.7% (271/780)

Tags

NPSC 2017-NPSC-fin

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 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
Submit
Back to Top