Array operations
Problem
You are given an array A consisting of N elements. Your task is to find the maximal subarray sum after applying the following operation exactly once:
- Select any subarray and set all the elements in it to zero.
Input format
- The first line contains an integer T denoting the number of test cases. For each test case:
- The first line of each test case contains an integer N denoting the number of elements in array A.
- The second line contains space-separated integers of array A.
Output format
Print T lines. For each test case, print a single line representing the maximal subarray sum after applying the operation no more than once.
Constraints
1≤T≤20000
1≤N≤500000
0≤|Ai|≤109∀i∈[1,N]
Sum of N over all test cases does not exceed 106
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
Initial array A=[-1,4,-1,2],if we choose this subarray [-1,4,-1,2] then modified array will be [-1,4,0,2] and the subarray with maximal sum is [-1,4,0,2] and sum is 4+0+2=6.
