CF1868E Min-Sum-Max

Tom 正在焦急地等待中考成绩。为了缓解他的紧张情绪，他的朋友 Daniel 决定和他玩一个叫做「分割数组」的游戏。 游戏规则是这样的：给定一个含有 $n$ 个整数的数组 $a$。记 $[l, r]$ 表示由整数 $a_l, a_{l+1}, \ldots, a_r$ 组成的子数组。 Tom 需要将这个数组分成若干连续的子数组 $[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$，每个整数都只能属于一个子数组。具体来说，需要满足以下条件： - 对于所有 $1 \le i \le m$，均有 $1 \le l_i \le r_i \le n$； - 子数组的开始和结束位置分别为 $l_1 = 1$ 和 $r_m = n$； - 对于所有 $1 < i \le m$，$l_i$ 必须等于 $r_{i-1} + 1$。 记 $s_i = \sum_{k=l_i}^{r_i} a_k$，也就是第 $i$ 个子数组中所有整数的和。在满足条件 $1 \le i \le j \le m$ 的前提下，需要保证： $$ \min_{i \le k \le j} s_k \le \sum_{k=i}^j s_k \le \max_{i \le k \le j} s_k. $$ Tom 希望将数组 $a$ 尽可能多地分割成更多的子数组。他让 Daniel 帮他找出最大可能的子数组数量。请帮助 Tom 找出这个最大值。

输入的第一行为一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。接下来是每个测试用例的详细描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 300$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示数组 $a$ 中的元素。 保证所有测试用例中的 $n$ 之和不超过 $1000$。

对于每个测试用例，输出一个整数，表示所有可能的分割方式中子数组的最大数量。

在第一个测试用例中，Daniel 可以将数组分成 $[-1]$ 和 $[5, 4]$，得到了 $s = [-1, 9]$。可以验证，对于任何 $i = j$，这个条件都自动满足；而对于 $i = 1, j = 2$，满足 $\min(-1, 9) \le (-1) + 9 \le \max(-1, 9)$。 在第二个测试用例中，若将数组分成 $[2023]$ 和 $[2043]$，则对于 $i = 1, j = 2$，有 $2023 + 2043 > \max(2023, 2043)$，所以子数组的最大数量为 $1$。 在第三个测试用例中，最优分割方式是 $[1, 4, 7], [-1], [5, -4]$。 在第四个测试用例中，最优分割方式是 $[-4, 0, 3, -18], [10]$。 在第五个测试用例中，Daniel 只能将数组划分为一个子数组。 **本翻译由 AI 自动生成**