Question
Balance Blitz
Kiran explored StarVale and discovered an array nums with n integers summing to zero.
He can perform an operation:
- pick two distinct indices i and j, reduce nums[i] by 1, and raise nums[j] by 1.
- If i < j, it’s free;
- otherwise, it costs one token.
Find the minimum tokens needed to make all elements zero.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains an integer n - the number of elements.
The next line contains n space separated integers nums1,…, numsn.
Each test case consists of two lines of input.
The first line of each test case contains an integer n - the number of elements.
The next line contains n space separated integers nums1,…, numsn.
Output
For each test case, print on new line, the minimum number of tokens he need to spend in order to make all the elements of the array equal to 0.
Example
Sample Input
1
4
-3 5 -3 1
Sample Output
3
Explanation
There's only test case. For this:
A possible strategy:
Do (i = 2, j = 3) three times (free), a = [−3, 2, 0, 1].
Do (i = 2, j = 1) two times (pay two coins), a=[−1, 0, 0, 1].
Do (i = 4, j = 1) one time (pay one coin), a=[0, 0, 0, 0].
1
4
-3 5 -3 1
Sample Output
3
Explanation
There's only test case. For this:
A possible strategy:
Do (i = 2, j = 3) three times (free), a = [−3, 2, 0, 1].
Do (i = 2, j = 1) two times (pay two coins), a=[−1, 0, 0, 1].
Do (i = 4, j = 1) one time (pay one coin), a=[0, 0, 0, 0].