卡牌游戏

题目描述

Orange在与Apple进行一场刺激的卡牌游戏。游戏规则是，每个人从自己的手牌序列中，选出一段连续的卡牌，其点数之和为这一次出牌的点数。

你的任务是，帮助Orange从他的手牌序列中，打出最大的点数。形式化的说，你需要最大化如下函数的值：

注意，你不可以不出牌。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行为一个整数 $n$，表示orange卡牌的点数序列 $a_i$ 的长度。 第二行为 $n$ 个整数 $a_i$。

数据范围

$1 \le n \le 10^5$ $|a_i| \le 10^4$ $\sum n \le 2 \times 10^5$

输出格式

对于每组测试数据，输出一个答案，占一行。

样例 #1

样例输入 #1

1
7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例解释

其中，最大的连续卡牌点数和为 $3+(-1)+2=4$