Better Maximal Sum
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You're given an array of N integer numbers.
The maximal sum of the array is the maximal sum of the elements of a nonempty consecutive subarray of this array. For example, the maximal sum of the array [1, -2, 3, -2, 5] is 6 because the sum of the subarray [3, -2, 5] is 6 and it is impossible to achieve greater subarray sum.
Now you're allowed to remove no more than one element from the given array. What is the maximal possible maximal sum of the resulting array you can achieve by doing so?
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in the given array.
The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.
For each test case, output a single line containing the maximal possible maximal sum of the array obtained by removing no more than one integer from the initial array.
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- -109 ≤ Ai ≤ 109
Input: 2 5 1 -2 3 -2 5 2 -1 -2 Output: 8 -1
Example case 1. As shown in the statement, the maximal sum of the initial array is 6, but if you remove the fourth element (i.e. -2), then the array [1, -2, 3, 5] will have subarray [3, 5] and the value of the maximal sum will be equal to 8.
|Tags||maxsum, medium, snckql16, xcwgf666|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.