MAXSUMSU - Maximum Subset Sum

Given an array, find the maximum subset sum of that array. A subset is a set of consecutive elements in the array.

Input

The first line of the input contains an integer t, denoting the number of test cases.

Each test case contains 2 lines. The first line consists of a number n, the number of elements in the array.

The second line consists of n numbers, the elements in the array.

All input fits in the integer size.

Output

Output a number for each test case, denoting the maximum subset sum of that array.

Example

Input:
2
4
1 -4 10 12
5
-1 5 6 -2 12

Sample Output
22
21

Explanation

22 and 21 are the maximum sums that can be obtained from the given array by adding consecutive numbers.


Added by:Aswin Murugesh
Date:2014-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Source

hide comments
2024-09-07 10:24:10
O(n) works ...
more hard problem with O(n) needed: 1796D CodeForces
2018-12-11 08:54:07
O(n*Logn) works
2018-09-01 16:48:40
It's not okay; got AC in 0.00s with bruteforce in slow language. This means people using this section for learning have no way of comparing algorithms, and worse still, might leave this one thinking O(n^3) is the bee's knees. This belongs to basics.

Also, subset of consecutive elements is probably better defined as subarray.
2017-08-15 09:11:39 avidcoder
Weak test cases! Since it is a tutorial problem. It's okay.

Last edit: 2017-08-15 09:33:11
2014-12-28 16:33:34 Francky
Description gives : "All input fits in the integer size", but you should be more precise ; please give explicit bounds. Integer doesn't mean anything ; is it 32bit, 64bit, or ... ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.