[Solution] Optimal Partition solution codeforces

Optimal Partition solution codeforces – You are given an array 𝑎a consisting of 𝑛n integers. You should divide 𝑎a into continuous non-empty subarrays (there are 2𝑛12n−1 ways to do that).

[Solution] Optimal Partition solution codeforces

Let 𝑠=𝑎𝑙+𝑎𝑙+1++𝑎𝑟s=al+al+1+…+ar. The value of a subarray 𝑎𝑙,𝑎𝑙+1,,𝑎𝑟al,al+1,…,ar is:

  • (𝑟𝑙+1)(r−l+1) if 𝑠>0s>0,
  • 00 if 𝑠=0s=0,
  • (𝑟𝑙+1)−(r−l+1) if 𝑠<0s<0.

What is the maximum sum of values you can get with a partition?

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡51051≤t≤5⋅105) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛51051≤n≤5⋅105).

The second line of each test case contains 𝑛n integers 𝑎1a1𝑎2a2, …, 𝑎𝑛an (109𝑎𝑖109−109≤ai≤109).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 51055⋅105.

[Solution] Optimal Partition solution codeforces

For each test case print a single integer — the maximum sum of values you can get with an optimal parition.

Example
input

Copy
5
3
1 2 -3
4
0 -2 3 -4
5
-1 -2 3 -1 -1
6
-1 2 -3 4 -5 6
7
1 -1 -1 1 -1 -1 1
output

Copy
1
2
1
6
-1

Optimal Partition solution codeforces

Test case 11: one optimal partition is [1,2][1,2][3][−3]1+2>01+2>0 so the value of [1,2][1,2] is 223<0−3<0, so the value of [3][−3] is 1−12+(1)=12+(−1)=1.

Test case 22: the optimal partition is [0,2,3][0,−2,3][4][−4], and the sum of values is 3+(1)=23+(−1)=2.

For Solution

Click here

Leave a Comment