回分類題庫
h188: G.最大不連續和問題
關鍵字: NPSC 2017 高中組決賽

測資點 : 8 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 30 Times / 21 Users | Submit : 246 Times / 34 Users | Accepted rate : 62%
題目加入時間 : 2018-10-08 10:52

Content: 简体中文

在數學中,某個數列的子數列是從最初數列通過去除某些元素,但不破壞餘下元素的相對位置(在前或在後)而形成的新數列。例如,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:

測試資料第一行包含一個正整數 T,代表有幾組測試資料。

每組測試資料第一行有一個數字 N,表示數列的長度。

第二行有 N 個整數 A1, A2, . . . , AN,表示數列。

Output:

每組測試資料輸出一個數字於一行,表示最大不連續和的值。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3
-1 -2 -3
6
1 1 1 -1 -3 10
10
9 4 3 8 1 5 10 7 2 6

Sample Output :

-4
13
54

Hint :

Author :

NPSC 2017 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum