Description
I don't have any pictures of Domo, so here is my cat. His name is Shiro
He sleep on my book to prevent me from studying, what a nice cat
You wan't to find the perfect bed for Shiro, so that he will not sleep on my book again
Given array A, the perfect bed is determined by the highest sum value from subarray between index i and j,
For example given array below:
The highest value is 7, which from index 2 to 6, as the sum is 4 + (-1) + (-2) + 1 + 5 = 7
HINT: You can try to use prefix sum to solve this question
Let S be an array of prefix sum A
then S[i] = A[0] + A[1] + A[2] + ... + A[i]
e.g. prefix sum of the above array will be:
[-2, -5, -1, -2, -4, -3, 2, -1]
and try to find the relation between the subarray
Let S be an array of prefix sum A
then S[i] = A[0] + A[1] + A[2] + ... + A[i]
e.g. prefix sum of the above array will be:
[-2, -5, -1, -2, -4, -3, 2, -1]
and try to find the relation between the subarray
Input
There are T test cases
each test case has an integer N on the first line and then followed by N integers in the next line: a0, a1, a2, ..., aN-1
1 <= T <= 100
1 <= N <= 50000
-109 <= ai <= 109
Output
For each testcase, print the maximum points of subarray, following by newline character