Min-Sum-Max
Contest: Codeforces Round 896 (Div. 1)
Difficulty rating: 3500
Tags: constructive algorithms, dp, greedy

Tom is waiting for his results of Zhongkao examination. To ease the tense atmosphere, his friend, Daniel, decided to play a game with him. This game is called "Divide the Array".

The game is about the array $$$a$$$ consisting of $$$n$$$ integers. Denote $$$[l,r]$$$ as the subsegment consisting of integers $$$a_l,a_{l+1},\ldots,a_r$$$.

Tom will divide the array into contiguous subsegments $$$[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$$$, such that each integer is in exactly one subsegment. More formally:

- For all $$$1\le i\le m$$$, $$$1\le l_i\le r_i\le n$$$;
- $$$l_1=1$$$, $$$r_m=n$$$;
- For all $$$1< i\le m$$$, $$$l_i=r_{i-1}+1$$$.

Denote $$$s_{i}=\sum_{k=l_i}^{r_i} a_k$$$, that is, $$$s_i$$$ is the sum of integers in the $$$i$$$-th subsegment. For all $$$1\le i\le j\le m$$$, the following condition must hold:

$$$$$$ \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 believes that the more subsegments the array $$$a$$$ is divided into, the better results he will get. So he asks Daniel to find the maximum number of subsegments among all possible ways to divide the array $$$a$$$. You have to help him find it.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\le t\le 50$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 300$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $$$a$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, Daniel can divide the array into $$$[-1]$$$ and $$$[5,4]$$$, and $$$s=[-1,9]$$$. It can be shown that for any $$$i=j$$$, the condition in the statement is already satisfied, and for $$$i=1,j=2$$$, we have $$$\min(-1,9)\le (-1)+9\le \max(-1,9)$$$.

In the second test case, if Daniel divides the array into $$$[2023]$$$ and $$$[2043]$$$, then for $$$i=1,j=2$$$ we have $$$2023+2043>\max(2023,2043)$$$, so the maximum number of subsegments is $$$1$$$.

In the third test case, the optimal way to divide the array is $$$[1,4,7],[-1],[5,-4]$$$.

In the fourth test case, the optimal to divide the array way is $$$[-4,0,3,-18],[10]$$$.

In the fifth test case, Daniel can only get one subsegment.

Example input:
8
3
-1 5 4
2
2023 2043
6
1 4 7 -1 5 -4
5
-4 0 3 -18 10
1
998244853
10
-4 2 5 -10 4 8 2 9 -15 7
7
-7 3 8 -9 -2 2 4
4
-5 5 -2 -5

Example output:
2
1
3
2
1
6
5
3

Editorial:
Let $$$s$$$ be the suffix sum array of array $$$a$$$. That is, $$$s_i=\sum_{j=1}^ia_i$$$ and $$$s_0=0$$$.
Let the partition point of the array be $$$r_0,r_1,\dots,r_m$$$, where $$$r_0=0$$$ and $$$r_m=n$$$.
Pick one of the maximums of $$$s_{r_0},s_{r_1},\dots,s_{r_m}$$$ and let it be $$$s_{r_x}$$$. Similarly, let the minimum be $$$s_{r_y}$$$.
If $$$|x-y|\geq 2$$$, there must be some $$$k$$$ ($$$k<x<y$$$) which satisfies that $$$s_{r_k}=s_{r_x}$$$ or $$$s_{r_k}=s_{r_y}$$$, or it's easy to see that the subsegment $$$[x+1,y]$$$ is invalid.
Using the induction method, we can show that there exists a pair $$$(i,i+1)$$$ such that $$$s_{r_i}$$$ and $$$s_{r_{i+1}}$$$ are the maximum and the minimum in a valid subsegment in a partition.
As a result, after enumerating $$$r_i,r_{i+1}$$$, the two parts $$$[1,r_i]$$$ and $$$[r_{i+1},n]$$$ are separate subproblems with constraints $$$s_{r_i}\leq r_t\leq s_{r_{i+1}}$$$.
Let $$$dp_{i,j,k,l}$$$ be the maximum number of $$$r_t$$$ we can select in the segment $$$[i,j]$$$ with all $$$k\leq s_{r_t}\leq l$$$ and positions $$$i,j$$$ must be selected.
Enumerate the maximum and minimum $$$s_{r_t}$$$ in all the selected $$$r_t$$$ and let them be $$$s_x$$$ and $$$s_y$$$. Then we get the transitions:
$$$$$$ \forall k\le s_x,l\ge s_y,dp_{i,j,k,l}\gets dp_{i,x,s_x,s_y}+dp_{y,j,s_x,s_y} $$$$$$
After compressing the coordinates of the array $$$s$$$ and changing the meaning of $$$k,l$$$ to the $$$k$$$-th,$$$l$$$-th small $$$s_i$$$ after coordinate compression, we can solve this problem in $$$\mathcal{O}(n^6)$$$, and $$$\mathcal{O}(n^4)$$$ with 2D prefix maximum.
Consider the optimization. It's easy to see that the states used in the transformation all satisfy $$$k=s_i$$$ or $$$l=s_i$$$ or $$$k=s_j$$$ or $$$l=s_j$$$.
Let's replace $$$dp_{i,j,s_i,k}$$$ by $$$f_{i,j,k}$$$ and replace $$$dp_{i,j,k,s_i}$$$ by $$$g_{i,j,k}$$$, and the transitions only relieve on $$$f_{i,j,k}$$$ and $$$g_{i,j,k}$$$, so the number of states was reduced to $$$\mathcal{O}(n^3)$$$.
Consider the transitions of $$$f_{i,j,k}$$$ as $$$g_{i,j,k}$$$ is similar. Since the minimum $$$s_{r_t}$$$ is greater than $$$s_i$$$ and the position $$$i$$$ must be selected, the minimum $$$s_{r_t}$$$ is $$$s_i$$$. Enumerate $$$x$$$ and let $$$s_x$$$ be the maximum $$$s_{r_t}$$$. We need to find the best position $$$y$$$ where $$$s_y$$$ is minimum, i.e. $$$s_y=s_i$$$ and transform the segment $$$[i,x],[y,j]$$$ or $$$[i,y],[x,j]$$$ to $$$[i,j]$$$. It's easy to see that selecting the first $$$s_y=s_i$$$ on the left/right of $$$x$$$ is always the best choice. Let $$$y_1,y_2$$$ be the first on the left/right, then the transitions are:
$$$$$$\forall k\ge s_x$$$$$$
$$$$$$f_{i,j,k}\leftarrow\max\{f_{i,y_1,s_x}+g_{x,j,s_i}\}$$$$$$
$$$$$$f_{i,j,k}\leftarrow\max\{f_{i,x,s_x}+f_{y_2,j,s_x}\}$$$$$$
Thus, the total time complexity is $$$\mathcal{O}(n^3)$$$ per test case.