最优划分

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

把整数数组 $a$ 划分成若干连续非空子数组。子数组 $[l,r]$ 的元素和为 $s$：若 $s>0$，价值为 $r-l+1$；若 $s=0$，价值为 $0$；若 $s<0$，价值为 $-(r-l+1)$。

求所有子数组价值之和的最大值。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n$，第二行包含 $n$ 个整数 $a_i$。

输出格式

每组输出一个整数答案。

样例输入 1

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

样例输出 1

1
2
1
6
-1

数据范围

• $1\le t\le5\times10^5$；
• $1\le n\le5\times10^5$；
• $-10^9\le a_i\le10^9$；
• 所有测试组的 $n$ 之和不超过 $5\times10^5$。