132. Day 2 PB. Liones的寶石

0 Judge

Code: 0


Liones的寶石

sprout

題目敘述

$Liones$的家中有許多閃閃發亮的寶石,一個接一個的直線排列在桌子上,每天$Liones$要出門為自己打扮妝點的時候,就會順手的從桌上抓取一些寶石來配戴在自己身上,凸顯自己的身分地位。每一個寶石對於$Liones$的造型都有不同的加成效果,稱為美感分數,比如說亮眼的紅寶石因為十分的耀眼,有100分的分數,而綠寶石與$Liones$平時的打扮十分不搭,穿上後會獲得$-87$的分數,大量扣分。$Liones$整體的美感分數會是所有穿著在身上寶石美感分數的總和。如果沒有穿著寶石的話則$Liones$的美感分數是$0$分。

不過$Liones$平時十分懶惰,她每一次只會抓一把擺放連續的寶石直接穿在身上,有的時候甚至算了都不拿,因此每一天$Liones$的美感分數都不一樣,$Liones$很好奇自己每天都這樣隨意的抓取寶石下,自己的美感分數最高會是多少,身為僕人的你可以幫忙計算嗎?

輸入說明

有多筆測資,但不超過$10$筆。每筆測資一開始有一個數字$N$,表示桌上有多少寶石,接下來下一行有$N$個整數$a_1,a_2,\cdots a_N$,依序表示桌上寶石的美感分數。

  • $1\leq N \leq 10^5$
  • $|a_i| \leq 100$。

輸出說明

對於每一筆測資輸出一行,為$Liones$可獲得最高的美感分數。

範例輸入

5
1 2 3 4 5
5
2 -9 3 1 -2
5
2 -1 3 9 -4

範例輸出

15
4
13

提示

Tip:測資很大、DP


Judge Setting

run-time limit: 100 ms
memory limit: 6553600 byte
測資數量: 0