题解

思路

设前缀和为 $s_i$，令 $dp_i$ 表示划分前 $i$ 个元素的最大价值。最后一段从 $j+1$ 到 $i$，其正负只由 $s_i$ 与 $s_j$ 的大小关系决定。把三种关系分别整理，就得到三个区间最大值查询。

做法

若 $s_j<s_i$，转移值为 $(dp_j-j)+i$；若相等，转移值为 $dp_j$；若 $s_j>s_i$，转移值为 $(dp_j+j)-i$。

离散化所有前缀和。用一棵树状数组维护较小前缀和值域上的 $dp_j-j$ 最大值，再在反向排名上维护较大前缀和值域上的 $dp_j+j$ 最大值；每个离散值另存相等时的最大 $dp_j$。计算 $dp_i$ 后把三个量插入结构。

子任务一可枚举 $i$ 之前的所有断点，得到 $O(n^2)$ 动态规划。子任务二中数组非负：若存在正数，把整个数组作为一段即可得到 $n$；若全为零，答案为零。

复杂度

每组时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。