Problem #1109 - ECNU Online Judge

单点时限: 5.0 sec

内存限制: 256 MB

给你一个序列 $a_{1}, a_{2}, \dots, a_{n}$ , 你的任务是去计算这个序列中和最大的一个子序列。例如，给你个序列 $(6, - 1, 5, 4, - 7)$ ，和最大的一个子序列是 $6 + (- 1) + 5 + 4 = 14$ 。

本题目是求最大（连续）子序列的和。

输入格式

在第一行输入一个数 $T (1 \leq T \leq 100000)$ 意思是输入序列的个数。然后后面 $T$ 行，每行开始一个数是 $N (1 \leq N \leq 100)$ ，这个序列有 $N$ 个数，然后接下来有 $N$ 个数 $(- 1000 \leq a_{i} \leq 1000)$ 。

输出格式

对每个测试，输出子序列和的最大值（此题子序列长度至少为 1）。

样例

Input

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Output

14
7

489 人解决，612 人已尝试。

889 份提交通过，共有 2434 份提交。

1.9 EMB 奖励。

创建: 18 年，1 月前.

修改: 7 年，6 月前.

最后提交: 1 月前.

来源: N/A

1109. Max Sum

输入格式

输出格式

样例

服务

开源

关于我们