Background

Original link: https://oier.team/problems/X4E。

Problem Description

For the following problem:

• You are given an array $a_1, \ldots, a_n$ of length $n$ (where $a_i$ may be negative) and a positive integer $m$.
• You need to choose at most $m$ index intervals $[l_j, r_j]$ of array $a$, and ensure that they are pairwise disjoint.
• You need to maximize the total sum of the elements inside the chosen intervals, i.e., maximize $\sum_j \sum_{i = l_j}^{r_j} a_i$.

Consider the following greedy algorithm (which is incorrect):

• Repeat the following process $m$ times:
• Among all intervals that do not intersect any currently chosen interval (including the empty interval), choose an interval with the maximum element sum.
  • If there are multiple intervals with the maximum element sum, choose any one of them.
  • Note: If the empty interval is chosen, it is equivalent to stopping the process, i.e., the number of chosen intervals is less than or equal to $m$.
• Take the sum of the elements in all non-empty intervals chosen in the process above as the answer.

Now you are given $n$ and the array $a_1, \ldots, a_n$. For each $m \in [1, n]$, find the maximum possible value and the minimum possible value of the answer (i.e., the total of interval sums) that this algorithm may produce.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains a positive integer $n$.
• The second line contains $n$ integers $a_1, \ldots, a_n$.

Output Format

For each test case:

• The first line contains $n$ integers. The $i$-th integer denotes the maximum value of the answer that the algorithm can obtain when $m = i$.
• The second line contains $n$ integers. The $i$-th integer denotes the minimum value of the answer that the algorithm can obtain when $m = i$.

5
5
1 -1 1 -1 1
5
2 -2 2 -1 2
6
3 1 -4 1 -5 9 
13
1 1 -4 5 -1 -4 1 9 1 9 -8 1 0
16
1 -8 2 -7 3 -6 4 -5 5 -4 4 -3 3 -2 2 -1

1 2 3 3 3
1 1 1 1 1
3 5 5 5 5
3 3 3 3 3
9 13 14 14 14 14
9 13 14 14 14 14
20 25 27 28 28 28 28 28 28 28 28 28 28
20 22 23 23 23 23 23 23 23 23 23 23 23
5 9 13 16 19 21 23 24 24 24 24 24 24 24 24 24
5 9 12 14 15 15 15 15 15 15 15 15 15 15 15 15

Hint

Sample Explanation

For the first test case:

• One way to achieve the maximum is to select intervals $[1,1],[3,3],[5,5],\varnothing,\varnothing$ in order.
• One way to achieve the minimum is to select intervals $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$ in order.

For the second test case:

• One way to achieve the maximum is to select intervals $[3,5],[1,1],\varnothing,\varnothing,\varnothing$ in order.
• One way to achieve the minimum is to select intervals $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$ in order.

Note: In the first update, you cannot choose intervals like $[1,1],[1,3],[3,3]$, because they do not satisfy that their interval sum is the maximum among all intervals in $S$ (i.e., $= 3$). In any update, you can never choose interval $[2,2]$, because its interval sum is $-2$, and $-2 < 0$ (which is the interval sum of the empty interval).

For the third test case, there is only one possible selection scheme, i.e., select intervals $[6,6],[1,2],[4,4],\varnothing,\varnothing,\varnothing$ in order.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le T \le 10^4$, $1 \le n \le 10^5$, $\sum n \le 5 \times 10^{5}$, and $|a_i| \le 10^9$。

Translated by ChatGPT 5