题目描述

给定若干组整数（有正有负），对每组数据求最大子段和：从这组数中选取一段连续的子序列，使它的元素之和最大。

特别规定：如果一组数据全部是负数，则答案为 0（相当于允许选取空子段）。

输入格式

第一行一个整数 $M$，表示有 $M$ 组测试数据。

接下来依次给出每组数据：

• 第一行一个整数 $N$，表示该组数据有 $N$ 个整数；
• 第二行 $N$ 个用空格隔开的整数 $a_1,a_2,\dots,a_N$。

输出格式

每组测试数据输出一行，一个整数，表示该组的最大子段和。

样例

3
8
-2 10 8 -4 7 5 -29 10
5
-1 -2 -3 -4 -5
4
1 -2 3 0

26
0
3

样例说明：

• 第 1 组：$10+8-4+7+5=26$，这是最大的连续子段和；
• 第 2 组：全部是负数，按约定答案为 $0$；
• 第 3 组：取最后两个数 $3+0=3$（取 $1-2+3+0=2$ 更小）。

数据范围

• $1 \le M \le 10$
• $1 \le N \le 100000$
• $|a_i| \le 10^5$
• 答案可能超过 32 位整数范围（最大约 $10^{10}$），请使用 long long

提示

如果不用动态规划而用穷举所有子段，时间复杂度为 $O(N^2)$，会超时； 请使用 $O(N)$ 的动态规划（Kadane 算法）。