Liones的寶石

題目敘述

$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