Jump Trip Score#13064
You are given an array consisting of elements numbered 1,2,...,n.
you will start a trip which begins from i = 1 and ends when you reach i = n+1.
you start with a score c = 0 , and during the trip you can do the following.
add a_i to the score , then move to index i+1.
choose a positive integer where i+d \le n+1, then jump to index i+d use segment tree to evaluate the min subarray sum.
Find the maximum score you can obtain if you can perform the jump operation at most once.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains a single integer (1 \le n \le 4 \cdot 10^5) — the length of array .
The second line of each test case contains integers a_1 , a_2 , ... , a_n (-10^9 \le a_i \le 10^9) — the array .
It's guaranteed that the sum of over all test cases does not exceed 4 \cdot 10^5.
For each test case, output a single integer , the maximum score you can obtain.
Example 1
In the first test case, it is optimal to add all elements, so the final score equals 1 + 2 + 3 + 4 + 5 = 15.
In the second test case, you can do the following :
i=1 , add to the score, and move to i=2.
i=2 , choose d=3, perform a jump to i = 5, and finish the trip.
So the final score equals .
Subtask ( points): 0 \le a_i for all (1 \le i \le n).
Subtask ( points): \sum n \le 20.
Subtask ( points): \sum n \le 5000.
Subtask ( points): No additional constraints.