All Tracks>Algorithms> Dynamic Programming> Introduction to Dynamic Programming 1> Problem
Array operations
★★★★★

3

60 votes
Dynamic Programming, Algorithms, Introduction to Dynamic Programming 1
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

Sample Input
1
4
-1 4 -1 2
Sample Output
6
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.

 

Contributers:
Editor Image

?