题解

思路

记前缀和 $s_i=\sum_{k=1}^{i}a_k$，并令 $f_i$ 为只考虑前 $i$ 个元素时的最大可选长度。

若不选择以 $i$ 结尾的区间，则有 $f_i\ge f_{i-1}$。若最后一个区间为 $[j+1,i]$，它合法当且仅当 $s_j\le s_i$，转移为

$$f_i=\max\left(f_{i-1},\ i+\max_{0\le j<i,\ s_j\le s_i}(f_j-j)\right).$$

因此只需动态维护所有已出现前缀和对应的 $f_j-j$，并支持前缀最大值查询。离散化前缀和后使用树状数组即可。

做法

• 若所有元素非负，整个数组本身合法，答案直接为 $n$。
• 当 $n\le2000$ 时，枚举所有 $j<i$ 完成 $O(n^2)$ 动态规划。
• 满分做法离散化 $s_0,s_1,\ldots,s_n$，树状数组维护前缀最大值。先加入 $j=0$ 的状态，再依次计算并加入每个 $i$。

复杂度

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