← 返回题单

题单练习树状数组

← 上一题下一题 →

A6899 | $最优分段$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个包含 $n$ 个整数的数组 $a$。你需要将 $a$ 划分为若干个连续且非空的子数组。 对任意子数组 $a_l,a_{l+1},\ldots,a_r$，令 $s=a_l+a_{l+1}+\cdots+a_r$，它的价值定义为： 如果 $s0$，价值为 $(r-l+1)$； 如果 $s=0$，价值为 $0$； 如果 $s0$，价值为 $-(r-l+1)$。 你可以用任意方式把整个数组切成若干段（每个元素必须属于且只属于一段）。问：所有子数组价值之和的最大值是多少？

输入格式

第一行一个整数 $t$，表示测试数据组数。 每组测试数据： 第一行一个整数 $n$； 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

每组测试数据输出一行一个整数，表示最大总价值。

输入输出样例

输入 #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

C++ 编辑器

输入

输出