Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rina Loves Shopping

By shajia · Limits 1s, 512 MB

Rina loves discounts. Whenever she gets a chance, she goes shopping and looks for the discount offers given by the shops. Recently, she has found a grocery shop that has announced an interesting offer. To avail of that offer, a consumer will need to purchase some products in a particular way.

There will be a row of products in the shop. Each of the products has a special point tag on it. The special point tag of a product indicates a relation between the manufacturing date and expiry date of that particular product. If the date of any product has expired already, the value will be negative. Otherwise, the value will be non-negative. A product that has been manufactured recently will have a bigger value than a product that is not that recent and is going to be expiring soon.

A consumer can buy all the products of the row or they can pick a contiguous sub-sequence of the products from the row. The target for the customers would be to pick the products in such a way that the summation of the special points of the products is maximum. If Rina manages to pick the products in this way, she will get a lifetime discount card. She will have to buy at least one product to be eligible for the offer.

Help Rina to buy products from the shop so that the summation of the points of the chosen products will be maximum.

Input

The first line of the input will contain an integer TT (1T10001≤T≤1000) that denotes the number of test cases. Then for each test case, there will be an integer AA (1A1000001 ≤ A ≤ 100000) — the number of products in that row. Then on the next line, there will be AA integers where each integer ai(a_i(109-10^9aia_i109 10^9 ) denotes the value points of the ithi-th product.

The maximum size of each of the input files will be at most 20MB.

Output

Print the maximum summation of the chosen products from the shop.

Samples

InputOutput
1
5
10 -7 -2 12 30
43
InputOutput
1
6
-9 -45 -25 6 2 1
9

Discussion

Statistics


80% Solution Ratio

naeem4265Earliest, 1M ago

HSTU_TREENITYFastest, 0.0s

user.106537Lightest, 131 kB

jahid_hridoyShortest, 280B

Submit

Login to submit

Editorial

DP Approach: This problem can be solved using Dynamic Programming. Let’s define two terms: dp[i]dp[i...

Toph uses cookies. By continuing you agree to our Cookie Policy.