794 . 投資建案
TopCoder
Description
天府城有一排土地由左到右編號 $1\sim N$，每塊土地有他蓋一棟建築帶來的價值。你想要在這裏投資一些土地並建起一些房屋，然而由於連續的房屋失火時容易蔓延，你希望投資的所有房屋不會恰形成一段完整的連續區間（也就是說，不存在 $l, r$ 使得對於所有房屋 $x$，$x$ 被你投資若且唯若 $l \le x \le r$），並且你不能全部不投資房屋。你的投資總收益是你在所有蓋房屋的土地上收益總和。請你回答在滿足條件下的最大收益。
Input Format
本題包含多筆測資，輸入第一行是一個整數 $T$，代表測資筆數。
每筆測資輸入兩行，第一行是一個整數 $N$，代表土地數量。
第二行有 $N$ 個空白分隔的整數 $a_i (1\le i\le N)$，代表投資第 $i$ 塊土地價值。
輸入保證 $T\le 10^ 5$，$3\le N\le 3\times 10^ 5$，$-1000\le a_i\le 1000$，且單筆輸入所有 $N$ 總和不超過 $3\times 10^ 5$。
Output Format
對於每筆測資輸出一行一個整數，代表最大投資收益。
Sample Input 1
2
5
-5 6 2 -4 0
5
-3 2 1 7 -4
5
-5 6 2 -4 0
5
-3 2 1 7 -4
Sample Output 1
8
9
9
Sample Input 2
1
3
-1 5 3
3
-1 5 3
Sample Output 2
2
Hints
Problem Source
NPSC
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~9 | 無額外限制 | 100 |