1109. Max Sum

单点时限: 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

462 人解决,577 人已尝试。

857 份提交通过,共有 2335 份提交。

1.9 EMB 奖励。

创建: 13 年,6 月前.

修改: 2 年,11 月前.

最后提交: 2 周,2 天前.

来源: N/A

题目标签