MAXSUMSU - Maximum Subset Sum

no tags 

Given an array, find the maximum subset sum of that array.

A Subset is a set of consecutive elements in the array.

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 a number for each test case, denoting the maximum subset sum of that array



Sample 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 arrays, by adding consecutive numbers.


hide comments
akshaybhatia95: 2018-12-11 08:54:07

O(n*Logn) works

nadstratosfer: 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.

avidcoder: 2017-08-15 09:11:39

Weak test cases! Since it is a tutorial problem. It's okay.

Last edit: 2017-08-15 09:33:11
Francky: 2014-12-28 16:33:34

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 ... ?


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