给定长度为 的整数序列 ，请将序列分成 段连续且非空的子数组，使得序列中的每个元素恰属于一个子数组。令 表示从左到右第 个子数组里的元素之和，对于每个 ，求下式的最大值。
更正式地，对于每个 ，令 以及 ，您需要找到 个整数 满足 ，并最大化下式的值。
有多组测试数据。第一行输入一个整数 表示测试数据组数，对于每组测试数据：
第一行输入一个整数 （）表示序列的长度。
第二行输入 个整数 （）表示序列。
保证所有数据 之和不超过 。
每组数据输出一行 个由单个空格分隔的整数 ，其中 表示 时的答案。
2 6 1 3 -4 5 -1 -2 1 100
2 4 5 3 1 -2 100
对于第一组样例数据，考虑 ，可以将序列分割为 。答案是 。
