You are given an array a consisting of n integers. You should divide a into continuous non-empty subarrays (there are 2ⁿ⁻¹ ways to do that).
Let  s=a_l+a_l+1+…+a_r . The value of a subarray a_l,a_l+1,…,a_r is:

• (r−l+1) if s>0 ,
• 0 if s=0 ,
• −(r−l+1) if s<0 .

What is the maximum sum of values you can get with a partition?


给定一个有 n 个数的数列 n，现在把它分成若干段。对于其中一段 a_l,a_l+1,…,a_r，设 s=a_l+a_l+1+…+a_r，则定义 a_l,a_l+1,…,a_r 一段的价值为：

• (r−l+1) if s>0 ,
• 0 if s=0 ,
• −(r−l+1) if s<0 .

显然，通过某些分段方式，可以使 a 中每段价值和最大，求这个最大价值。

The input consists of multiple test cases. The first line contains a single integer t (1≤t≤5⋅10⁵ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤5⋅10⁵ ).
The second line of each test case contains  n integers a1 , a2 , ..., an ( −10⁹≤ai≤10⁹ ).
It is guaranteed that the sum of n over all test cases does not exceed 5⋅10⁵ .

For each test case print a single integer — the maximum sum of values you can get with an optimal parition.

Test case 1 : one optimal partition is [1,2] , [−3] . 1+2>0 so the value of [1,2] is 2 . −3<0 , so the value of [−3] is −1 . 2+(−1)=1 .
Test case 2 : the optimal partition is [0,−2,3] ,[−4] , and the sum of values is 3+(−1)=2 .

动态规划 数据结构 线段树 树状数组