Given an array containing positive and negative numbers. The array represents checkpoints from one end to other end of street. Positive and negative values represent amount of energy at that checkpoint. Positive numbers increase the energy and negative numbers decrease. Find the minimum initial energy required to cross the street such that Energy level never becomes 0 or less than 0.
Note :  The value of minimum initial energy required will be 1 even if we cross street successfully without loosing energy to less than and equal to 0 at any checkpoint. The 1 is required for initial check point.
 
Example 1:
Input
N = 5
A[] = {4, -10, 4, 4, 4}
Output
7
Explanation
By having an initial energy of 7 we can
make sure that all the checkpoints are
visited and the fuel never reaches 0
or less value.
 
Example 2:
Input
N = 5
A[] = {3, 5, 2, 6, 1}
Output
1
Explanation
We need at least 1 initial energy
to reach first checkpoint.
Your Task:
You don't need to print anything, printing is done by the driver code itself. You need to complete the function minEnergy() which takes the array A[] and its size N as inputs and returns the minimum initial energy required to cross the street.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
-10^{3} ≤ A[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def minEnergy(self, a, n):
         # Your code goes here

Solutions:
class Solution:

	def minEnergy(self, a, n):
		initMinEnergy = 0
		currEnergy = 0
		flag = 0
		for i in range(n):
			currEnergy += a[i]
			if currEnergy <= 0:
				initMinEnergy += abs(currEnergy) + 1
				currEnergy = 1
				flag = 1
		return 1 if flag == 0 else initMinEnergy


class Solution:

	def minEnergy(self, a, n):
		m = 1
		e = 0
		for i in a:
			e += i
			m = min(m, e)
		if m <= 0:
			return -m + 1
		return 1


class Solution:

	def minEnergy(self, a, n):
		mini = 0
		summa = 0
		for item in a:
			summa += item
			mini = min(mini, summa)
		return 1 - mini


import math

class Solution:

	def minEnergy(self, a, n):
		sum = 0
		globalMin = math.inf
		for item in a:
			sum += item
			if sum < globalMin:
				globalMin = sum
		return max(1 - globalMin, 1)


class Solution:

	def minEnergy(self, a, n):
		mini = 0
		(cur, flag) = (0, 0)
		for i in range(n):
			cur += a[i]
			if cur <= 0:
				mini += abs(cur) + 1
				cur = 1
				flag = 1
		if flag == 0:
			return 1
		else:
			return mini


class Solution:

	def minEnergy(self, a, n):
		l = []
		sum = 0
		temp = 0
		for i in range(n):
			sum += a[i]
			temp = min(temp, sum)
		if temp <= 0:
			return abs(temp) + 1
		else:
			return 1


class Solution:

	def minEnergy(self, a, n):
		mini = 1
		sum = 0
		for i in range(n):
			sum += a[i]
			if sum < 0:
				mini += abs(sum)
				sum = 0
		return mini


class Solution:

	def minEnergy(self, a, n):
		required = 1
		start = 1
		for i in range(n):
			start = start + a[i]
			if start <= 0:
				required += abs(start) + 1
				start = 1
		return required


class Solution:

	def minEnergy(self, a, n):
		curr_eng = 0
		req_eng = 0
		for i in range(n):
			curr_eng += a[i]
			if curr_eng < 0:
				req_eng += abs(curr_eng)
				curr_eng = 0
		return req_eng + 1


class Solution:

	def minEnergy(self, a: list, n: int) -> int:
		minimum = 0
		summation = 0
		for i in range(n):
			summation += a[i]
			minimum = minimum if minimum < summation else summation
		return abs(minimum) + 1


class Solution:

	def minEnergy(self, a, n):
		summ = 0
		neg = 0
		for e in a:
			summ = summ + e
			if summ < neg:
				neg = summ
		return -neg + 1


class Solution:

	def minEnergy(self, a, n):
		flag = 0
		summ = 0
		current_energy = 0
		for i in range(n):
			summ += a[i]
			if summ <= 0:
				current_energy += abs(summ) + 1
				summ = 1
				flag = 1
		if flag == 0:
			return 1
		else:
			return current_energy


class Solution:

	def minEnergy(self, a, n):
		ans = 0
		total = 0
		flag = 0
		for i in range(n):
			total += a[i]
			if total <= 0:
				ans += abs(total) + 1
				total = 1
				flag = 1
		return 1 if flag == 0 else ans


class Solution:

	def minEnergy(self, a, n):
		energy = 1
		summ = 1
		for x in range(n):
			if a[x] < 0:
				if summ + a[x] <= 0:
					energy += abs(summ + a[x]) + 1
					summ = 1
				else:
					summ += a[x]
			else:
				summ += a[x]
		return energy


class Solution:

	def minEnergy(self, a, n):
		energy = 0
		total = 0
		for i in a:
			total += i
			if total < 0:
				energy += abs(total)
				total = 0
		energy += 1
		return energy


class Solution:

	def minEnergy(self, a, n):
		s = 0
		t = 100
		for i in range(n):
			s += a[i]
			t = min(t, s)
		if t <= 0:
			return abs(t) + 1
		else:
			return 1


class Solution:

	def minEnergy(self, a, n):
		s = 0
		m = 9999999999
		for i in a:
			s += i
			if s < m:
				m = s
		if m > 0:
			return 1
		return -m + 1


class Solution:

	def minEnergy(self, a, n):
		curr_sum = 0
		energy = 0
		flag = 1
		for i in range(n):
			curr_sum += a[i]
			if curr_sum <= 0:
				energy += abs(curr_sum) + 1
				curr_sum = 1
				flag = 0
		if flag:
			return 1
		return energy


class Solution:

	def minEnergy(self, a, n):
		x = []
		c = 0
		for i in a:
			c += i
			x.append(c)
		if min(x) > 0:
			return 1
		return abs(min(x)) + 1


class Solution:

	def minEnergy(self, a, n):
		e = 0
		s = 0
		for x in a:
			s += x
			if s <= 0:
				e = e + abs(s)
				s = 0
		return 1 + e


class Solution:

	def minEnergy(self, a, n):
		ans = 1
		curr_e = 0
		for i in a:
			if i > 0:
				curr_e += i
			elif curr_e < -i:
				ans += abs(i) - curr_e
				curr_e = 0
			else:
				curr_e += i
		return ans


class Solution:

	def minEnergy(self, a, n):
		current = 0
		ans = 0
		for e in a:
			current += e
			if current <= 0:
				ans += abs(current) + 1
				current = 1
		return ans if ans else 1

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.minEnergy(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def minEnergy(self, a, n):
		(initMin, curr, flag) = (0, 0, 0)
		for i in range(0, n):
			curr += a[i]
			if curr <= 0:
				initMin += abs(curr) + 1
				curr = 1
				flag = 1
		return 1 if flag == 0 else initMin


class Solution:

	def minEnergy(self, a, n):
		req = 0
		s = 0
		for i in a:
			s += i
			if s <= 0:
				req += abs(s) + 1
				s = 1
		if req == 0:
			return 1
		else:
			return req


class Solution:

	def minEnergy(self, a, n):
		c = 0
		for i in a:
			if i > 0:
				c = c + 1
		if c == len(a):
			return 1
		elif c == 0:
			s = 0
			for i in a:
				s = s + abs(i)
			return s + 1
		else:
			ie = 0
			tem = 0
			for i in a:
				tem = tem + i
				if tem <= 0:
					ie = ie + abs(tem) + 1
					tem = 1
			return ie


class Solution:

	def minEnergy(self, a, n):
		energy_sum = 0
		temp_value = 9999
		for i in a:
			energy_sum += i
			temp_value = min(energy_sum, temp_value)
		if temp_value < 0:
			return abs(temp_value) + 1
		return 1


class Solution:

	def minEnergy(self, a, n):
		energy_sum = 0
		initial_energy = 1000
		for energy in a:
			energy_sum += energy
			initial_energy = min(energy_sum, initial_energy)
		if initial_energy < 0:
			return abs(initial_energy) + 1
		return 1


class Solution:

	def minEnergy(self, a, n):
		current_energy = 0
		res = 0
		for e in a:
			current_energy += e
			if current_energy <= 0:
				res += -1 * current_energy
				current_energy = 0
		return res + 1


class Solution:

	def minEnergy(self, a, n):
		c = 1
		ini = 1
		for i in a:
			if ini + i > 0:
				ini += i
			else:
				c += abs(ini + i) + 1
				ini = 1
		return c


class Solution:

	def minEnergy(self, arr, n):
		ans = 1
		s = 0
		for i in range(0, n):
			s += arr[i]
			if s < 0:
				ans += abs(s)
				s = 0
		return ans


class Solution:

	def minEnergy(self, a, n):
		theEnergy = 0
		currEnergy = 0
		for x in a:
			currEnergy += x
			if currEnergy < 1:
				theEnergy = theEnergy + abs(currEnergy) + 1
				currEnergy = 1
		if theEnergy == 0:
			theEnergy = 1
		return theEnergy


class Solution:

	def minEnergy(self, a, n):
		m = 10 ** 9
		s = 0
		for i in a:
			s += i
			m = min(m, s)
		if m <= 0:
			return abs(m) + 1
		return 1


class Solution:

	def minEnergy(self, a, n):
		ime = 0
		ce = 0
		for i in range(n):
			ce = ce + a[i]
			if ce <= 0:
				ime += abs(ce) + 1
				ce = 1
		if ime == 0:
			return 1
		return ime


import sys

class Solution:

	def minEnergy(self, a, n):
		sum = 0
		temp = 99
		for i in range(n):
			sum += a[i]
			temp = min(temp, sum)
		if temp <= 0:
			return abs(temp) + 1
		else:
			return 1


class Solution:

	def minEnergy(self, a, n):
		ans = 0
		total = 0
		flag = 0
		for x in a:
			total += x
			if total <= 0:
				flag = 1
				ans += abs(total) + 1
				total = 1
		if flag == 1:
			return ans
		return ans + 1


class Solution:

	def minEnergy(self, a, n):
		init_energy = 1
		my_sum = 0
		for i in range(n):
			my_sum += a[i]
			if my_sum + init_energy <= 0:
				init_energy = abs(my_sum) + 1
		return init_energy


class Solution:

	def minEnergy(self, a, n):
		e = 0
		min_e = 0
		for el in a:
			e += el
			min_e = min(e, min_e)
		return max(1, -min_e + 1)