2048 . G.最大不連續和問題
TopCoder
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$ 個整數$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
-1 -2 -3
Sample Output 1
-4
Sample Input 2
6
1 1 1 -1 -3 10
1 1 1 -1 -3 10
Sample Output 2
13
Sample Input 3
10
9 4 3 8 1 5 10 7 2 6
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 |