A6899. 最优分段
编程题
提高+/省选-
知识点
题目描述
给定一个包含 $n$ 个整数的数组 $a$。你需要将 $a$ 划分为若干个连续且非空的子数组。
对任意子数组 $a_l,a_{l+1},\ldots,a_r$，令 $s=a_l+a_{l+1}+\cdots+a_r$，它的价值定义为：
- 如果 $s>0$，价值为 $(r-l+1)$；
- 如果 $s=0$，价值为 $0$；
- 如果 $s<0$，价值为 $-(r-l+1)$。
你可以用任意方式把整个数组切成若干段（每个元素必须属于且只属于一段）。问：所有子数组价值之和的**最大值**是多少？
对任意子数组 $a_l,a_{l+1},\ldots,a_r$，令 $s=a_l+a_{l+1}+\cdots+a_r$，它的价值定义为：
- 如果 $s>0$，价值为 $(r-l+1)$；
- 如果 $s=0$，价值为 $0$；
- 如果 $s<0$，价值为 $-(r-l+1)$。
你可以用任意方式把整个数组切成若干段（每个元素必须属于且只属于一段）。问：所有子数组价值之和的**最大值**是多少？
输入格式
第一行一个整数 $t$，表示测试数据组数。
每组测试数据：
- 第一行一个整数 $n$；
- 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。
每组测试数据：
- 第一行一个整数 $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
1 2 1 6 -1
说明/提示
## 样例解释
例如第一组：可以分成 $[1,2]$ 和 $[-3]$。
- $1+2>0$，价值是 $2$
- $-3<0$，价值是 $-1$
总价值 $2+(-1)=1$，这是最优答案。
例如第一组：可以分成 $[1,2]$ 和 $[-3]$。
- $1+2>0$，价值是 $2$
- $-3<0$，价值是 $-1$
总价值 $2+(-1)=1$，这是最优答案。