We define subsequence as any subset of an array.  We define a subarray as a contiguous subsequence in an array.  

Given an array, find the maximum possible sum among:

all nonempty subarrays. 
all nonempty subsequences. 

Print the two values as space-separated integers on one line. 

Note that empty subarrays/subsequences should not be considered. 

Example 

$arr=[-1,2,3,-4,5,10]$   

The maximum subarray sum is comprised of elements at inidices $\left[1-5\right]$.  Their sum is $2+3+-4+5+10=16$.  The maximum subsequence sum is comprised of elements at indices $[1,2,4,5]$ and their sum is $2+3+5+10=20$.  

Function Description  

Complete the maxSubarray function in the editor below.    

maxSubarray has the following parameter(s):  

int arr[n]: an array of integers  

Returns  

int[2]: the maximum subarray and subsequence sums  

Input Format

The first line of input contains a single integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.

The first line of each test case contains a single integer $n$. 

The second line contains $n$ space-separated integers $arr\left[i\right]$ where $0\leq i<n$.   

Constraints

$1\leq t\leq10$
$1\leq n\leq10^5$   
$-10^4\leq arr[i]\leq10^4$   

The subarray and subsequences you consider should have at least one element.

Sample Input 0
2
4
1 2 3 4
6
2 -1 2 3 4 -5

Sample Output 0
10 10
10 11

Explanation 0

In the first case: The maximum sum for both types of subsequences is just the sum of all the elements since they are all positive.

In the second case: The subarray $[2,-1,2,3,4]$ is the subarray with the maximum sum, and $[2,2,3,4]$ is the subsequence with the maximum sum.

Sample Input 1
1
5
-2 -3 -1 -4 -6

Sample Output 1
-1 -1

Explanation 1

Since all of the numbers are negative, both the maximum subarray and maximum subsequence sums are made up of one element, $-1$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
test = int(input())
while test:
	test -= 1
	input()
	num_list = [int(x) for x in input().split()]
	max_sum = 0
	tmp_sum = 0
	max_non_contg = 0
	flg = False
	mx = max(num_list)
	if mx < 0:
		print(str(mx) + ' ' + str(mx))
		continue
	for i in range(len(num_list)):
		if tmp_sum < 0:
			tmp_sum = 0
		tmp_sum += num_list[i]
		if tmp_sum > max_sum:
			max_sum = tmp_sum
		if num_list[i] > 0:
			max_non_contg += num_list[i]
	print(str(max_sum) + ' ' + str(max_non_contg))


for i in range(int(input())):
	input()
	l = list(map(int, input().split()))
	r1 = sum(filter(lambda x: x > 0, l))
	if r1 <= 0:
		r1 = max(l)
	r2 = 0
	t = 0
	for j in l:
		t += j
		t = max(0, t)
		r2 = max(r2, t)
	if r2 <= 0:
		r2 = max(l)
	print('%i %i' % (r2, r1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a[0]
	cur = a[0]
	for i in range(1, n):
		cur = max(cur + a[i], a[i])
		ans = max(ans, cur)
	a = sorted(a, reverse=True)
	ans2 = a[0]
	for i in range(1, n):
		if a[i] > 0:
			ans2 += a[i]
	print(ans, ans2)


def MaxSub(A, N):
	max_ending_here = max_so_far = 0
	for x in A:
		max_ending_here = max(0, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	if max_so_far == 0:
		max_so_far = max(A)
	return str(max_so_far)

def MaxSubNonCont(A, N):
	tot = 0
	for x in A:
		if x > 0:
			tot += x
	if tot == 0:
		tot = max(A)
	return str(tot)
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	print(MaxSub(A, N) + ' ' + MaxSubNonCont(A, N))


def max_sum(l):
	all_negative = True
	biggest_neg = -(1 << 30)
	current_sum = 0
	best_sum = 0
	p_sum = 0
	for e in l:
		if e >= 0:
			all_negative = False
		if e < 0 and e > biggest_neg:
			biggest_neg = e
		k = current_sum + e
		current_sum = k if k > 0 else 0
		if current_sum > best_sum:
			best_sum = current_sum
		if e > 0:
			p_sum += e
	if all_negative:
		return (biggest_neg, biggest_neg)
	return (best_sum, p_sum)

def main():
	import sys
	T = int(sys.stdin.readline().strip())
	for i in range(T):
		_ = sys.stdin.readline()
		l = [int(x) for x in sys.stdin.readline().strip().split()]
		(csum, ncsum) = max_sum(l)
		print('{0} {1}'.format(csum, ncsum))
main()


def solve(A):
	max_ending_here = max_so_far = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far
for case in range(int(input())):
	input()
	a = list(map(int, input().split()))
	max_a = max(a)
	print(solve(a), sum((i for i in a if i > 0)) if max_a > 0 else max_a)


T = int(input())
for ncase in range(T):
	N = int(input())
	sq = [int(i) for i in input().split(' ')]
	ans1 = 0
	ans2 = 0
	sum = 0
	minsum = 0
	for i in range(N):
		sum += sq[i]
		minsum = sum if minsum > sum else minsum
		ans1 = sum - minsum if sum - minsum > ans1 else ans1
		ans2 += 0 if sq[i] < 0 else sq[i]
	if ans2 == 0:
		ans1 = max(sq)
		ans2 = max(sq)
	print(ans1, ans2)


for _ in range(int(input())):
	a = int(input())
	L = list(map(int, input().split(' ')))
	current_val = 0
	current_index = -1
	best_start_index = -1
	best_end_index = -1
	best_sum = 0
	s = 0
	c = False
	for i in range(a):
		val = current_val + L[i]
		if val > 0:
			if current_val == 0:
				current_index = i
			current_val = val
		else:
			current_val = 0
		if current_val > best_sum:
			best_start_index = current_index
			best_end_index = i
			best_sum = current_val
		if L[i] > 0:
			s = s + L[i]
			c = True
	if not c:
		best_sum = max(L)
		s = best_sum
	print(best_sum, s)


t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	cur_sum = 0
	best_sum = 0
	sum_ = 0
	for y in a:
		if y >= 0:
			cur_sum += y
			sum_ += y
		elif cur_sum + y < 0:
			if best_sum < cur_sum:
				best_sum = cur_sum
			cur_sum = 0
		else:
			if best_sum < cur_sum:
				best_sum = cur_sum
			cur_sum += y
	else:
		if cur_sum > best_sum:
			best_sum = cur_sum
	a.sort()
	if a[len(a) - 1] < 0:
		best_sum = a[len(a) - 1]
		sum_ = a[len(a) - 1]
	print(best_sum, sum_)


import sys
n = int(sys.stdin.readline())

def result():
	sys.stdin.readline()
	arr = list(map(int, sys.stdin.readline().split(' ')))

	def positive(i):
		return i > 0

	def first_res(arr):
		s = arr[0]
		tmp_s = 0
		for i in arr:
			tmp_s += i
			tmp_s = max(i, tmp_s)
			s = max(s, tmp_s)
		return s

	def second_res(arr):
		tmp_arr = sorted(arr)
		positive_arr = list(filter(positive, arr))
		if len(positive_arr) > 0:
			return sum(positive_arr)
		else:
			return tmp_arr[-1]
	return '%d %d' % (first_res(arr), second_res(arr))
for i in range(0, n):
	print(result())


import sys

def run_max_subarray():
	for line in sys.stdin.readlines()[2::2]:
		arr = [int(x) for x in line.split(' ')]
		print(max_contiguous_subarray(arr), max_subarray(arr))

def max_contiguous_subarray(arr):
	(m_i, m, pos) = (0, 0, False)
	for x in arr:
		if x >= 0:
			pos = True
		m_i = max(0, m_i + x)
		m = max(m, m_i)
	if not pos:
		return max(arr)
	return m

def max_subarray(arr):
	(tot, pos) = (0, False)
	for x in arr:
		if x >= 0:
			pos = True
			tot += x
	if not pos:
		return max(arr)
	return tot
run_max_subarray()


import sys
in_trails = int(input())
for trial in range(in_trails):
	in_len = int(input())
	arr = [int(x) for x in input().split(' ')]
	max_ending_here = max_cont = max_non = arr[0]
	for idx in range(1, len(arr)):
		num = arr[idx]
		max_ending_here = max(num, max_ending_here + num)
		max_cont = max(max_cont, max_ending_here)
		max_non = max(max(max_non, num), max_non + num)
	print('{} {}'.format(max_cont, max_non))


def solve(A):
	if max(A) <= 0:
		return (max(A), max(A))
	(x, y, s, b) = (0, 0, 0, 0)
	for (i, a) in enumerate(A):
		if s == 0 and a > 0:
			x = i
		s += a
		if s < 0:
			s = 0
		if s > b:
			b = s
	return (b, sum((a for a in A if a > 0)))
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(_) for _ in input().split()]
	print('%d %d' % solve(A))


case = int(input())
for i in range(case):
	size = int(input())
	ar = [int(j) for j in input().strip().split()]
	maxSum1 = 0
	sum1 = 0
	sum2 = 0
	maxElement = ar[0]
	for k in range(size):
		if sum1 + ar[k] >= 0:
			sum1 += ar[k]
			if sum1 > maxSum1:
				maxSum1 = sum1
		else:
			sum1 = 0
		if ar[k] >= 0:
			sum2 += ar[k]
		if ar[k] > maxElement:
			maxElement = ar[k]
	if maxElement < 0:
		print(maxElement, maxElement)
	else:
		print(maxSum1, sum2)


t = int(input())
for T in range(t):
	N = int(input())
	a = [int(s) for s in input().split()]
	bestEndHere = 0
	bestMax = 0
	bestNonContig = 0
	for e in a:
		bestEndHere = max(bestEndHere + e, 0)
		bestMax = max(bestEndHere, bestMax)
		bestNonContig += 0 if e < 0 else e
	if max(a) < 0:
		print(max(a), max(a))
	else:
		print(bestMax, bestNonContig)


cases = int(input())
for case in range(0, cases):
	size = int(input())
	nums = [int(i) for i in input().split()]
	current_sum = 0
	best_sum = 0
	current_index = -1
	best_start_index = -1
	best_end_index = -1
	sums = 0
	for i in range(size):
		current_num = nums[i]
		if current_num > 0:
			sums += current_num
		val = current_sum + current_num
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_start_index = current_index
			best_sum = current_sum
			best_end_index = i
	contiguous_sum = sum(nums[best_start_index:best_end_index + 1])
	if sums == 0:
		sums = max(nums)
		contiguous_sum = sums
	print(contiguous_sum, sums)


def max_subarray(num):
	current_max = num[0]
	global_max = num[0]
	for x in num[1:]:
		current_max = max(x, current_max + x)
		global_max = max(global_max, current_max)
	return global_max
T = int(input())
for i in range(T):
	N = int(input())
	num = str(input())
	num = [int(n) for n in num.split(' ')]
	nc_sum = 0
	for i in range(N):
		if num[i] > 0:
			nc_sum = nc_sum + num[i]
	if nc_sum == 0:
		nc_sum = max(num)
	c_sum = max_subarray(num)
	print(c_sum, nc_sum)


def max_sum(L):
	cur_sum = 0
	best_sum = 0
	cur_index = -1
	best_start_index = -1
	best_end_index = -1
	min_v = 0
	for i in range(len(L)):
		if min_v == 0 or min_v < L[i]:
			min_v = L[i]
		val = cur_sum + L[i]
		if val > 0:
			cur_sum = val
			if cur_sum == 0:
				cur_index = i
		else:
			cur_sum = 0
		if cur_sum > best_sum:
			best_sum = cur_sum
			best_start_index = cur_index
			best_end_index = i
	if best_sum > 0:
		return best_sum
	else:
		return min_v

def max_nsum(L):
	best_sum = 0
	min_v = 0
	for v in L:
		if v > 0:
			best_sum += v
		elif min_v == 0 or min_v < v:
			min_v = v
	if best_sum == 0:
		return min_v
	else:
		return best_sum
T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split()]
	print(max_sum(arr), max_nsum(arr))


def max_subarray_contiguous(L):
	min_val = min(L)
	max_val = max(L)
	current_sum = 0
	best_sum = min_val
	current_index = 0
	best_start_index = 0
	best_end_index = 0
	for i in range(len(L)):
		val = current_sum + L[i]
		if L[i] > val:
			current_index = i
			current_sum = L[i]
		else:
			current_sum = val
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return L[best_start_index:best_end_index + 1]

def max_subarray_non_contiguous(L):
	return max_subarray_contiguous(sorted(L))

def parse_case():
	n = int(input())
	L = [int(i) for i in input().split(' ')]
	print(sum(max_subarray_contiguous(L)), end=' ')
	print(sum(max_subarray_non_contiguous(L)))
for t in range(int(input())):
	parse_case()


t = int(input())

def print_max(a):
	max = 0
	max_a = 0
	max_b = 0
	temp = 0
	for (i, x) in enumerate(a):
		if i == 0:
			max = x
		if max < x:
			max = x
		if x > 0:
			max_a += x
		temp += x
		if temp < 0:
			temp = 0
		elif temp > max_b:
			max_b = temp
	if max_a == 0:
		print(str(max) + ' ' + str(max))
	else:
		print(str(max_b) + ' ' + str(max_a))
while t > 0:
	t -= 1
	c = int(input())
	a = [int(i) for i in input().split()]
	print_max(a)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	line = input().split()
	lst = []
	for num in line:
		lst.append(int(num))
	mn = 0
	ans = ans2 = sm = lst[0]
	for i in range(1, N):
		mn = min(mn, sm)
		sm += lst[i]
		ans = max(ans, sm - mn)
		ans2 = max(ans2, ans2 + lst[i], lst[i])
	print(str(ans) + ' ' + str(ans2))


def max_subarray(array):
	optimal = array
	max_noncontig = 0
	for (i, elem) in enumerate(array):
		optimal[i] = max(optimal[i - 1] + elem, elem) if i else elem
		if elem > 0:
			max_noncontig += elem
	if max_noncontig == 0:
		max_noncontig = max(array)
	return (max(optimal), max_noncontig)
num_cases = int(input())
for case in range(num_cases):
	num_elems = int(input())
	array = [int(x) for x in input().split()]
	(max_contig, max_noncontig) = max_subarray(array)
	print(max_contig, max_noncontig)


def sum_max_subarray(array):
	sum = 0
	max_sum = None
	for a in array:
		sum += a
		if max_sum is None or max_sum < sum:
			max_sum = sum
		if sum < 0:
			sum = 0
	return max_sum

def sum_max_subset(set):
	m = max(set)
	if m <= 0:
		return m
	else:
		return sum([i for i in set if i > 0])
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(sum_max_subarray(a), sum_max_subset(a))


lists = []
T = int(input())
for i in range(0, T):
	N = int(input())
	lists = [int(i) for i in input().split()]
	maxim_curr = 0
	maxim = 0
	maxim2 = 0
	for i in range(0, len(lists)):
		if lists[i] < 0:
			maxim_curr = maxim_curr + lists[i]
			if maxim_curr < 0:
				maxim_curr = 0
		else:
			maxim_curr = maxim_curr + lists[i]
			maxim2 = maxim2 + lists[i]
		if maxim < maxim_curr:
			maxim = maxim_curr
	if maxim2 == 0:
		maxim2 = max(lists)
	if maxim == 0:
		maxim = max(lists)
	print(maxim, maxim2)


for i in range(int(input())):
	input()
	seq = [int(j) for j in input().split(' ')]
	if max(seq) < 0:
		print(max(seq), max(seq))
		continue
	best_yet = 0
	start = 0
	curr = 0
	for end in range(len(seq)):
		curr += seq[end]
		if curr < 0:
			curr = 0
			start = end
		best_yet = max(best_yet, curr)
	print(best_yet, sum((i for i in seq if i > 0)))


def msa(a):
	c_sum = 0
	t_sum = 0
	nc_sum = 0
	for i in a:
		t_sum += i
		if t_sum > c_sum:
			c_sum = t_sum
		if t_sum < 0:
			t_sum = 0
		if i > 0:
			nc_sum += i
	if nc_sum == 0:
		nc_sum = max(a)
		c_sum = nc_sum
	return (c_sum, nc_sum)
t = int(input())
for i in range(t):
	input()
	a = [int(x) for x in input().strip().split()]
	(c_sum, nc_sum) = msa(a)
	print(c_sum, nc_sum)


t = int(input())
for x in range(t):
	n = int(input())
	a = input().split()
	for i in range(len(a)):
		a[i] = int(a[i])
	non = 0
	for i in a:
		if i > 0:
			non += i
	if non == 0:
		tmp = a[0]
		for i in a:
			if i > tmp:
				tmp = i
		non = tmp
	me = a[0]
	mx = a[0]
	for i in a[1:]:
		me = max(i, me + i)
		mx = max(mx, me)
	print(str(mx) + ' ' + str(non))


t = int(input())
for tests in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	best_sum1 = 0
	current_sum = 0
	best_sum2 = 0
	max_val = a[0]
	for i in range(n):
		if a[i] > max_val:
			max_val = a[i]
		if a[i] > 0:
			best_sum2 += a[i]
		val = current_sum + a[i]
		if val > 0:
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum1:
			best_sum1 = current_sum
	if max_val > 0:
		print(best_sum1, best_sum2)
	else:
		print(max_val, max_val)


T = int(input())
tests = []
for t in range(T):
	N = int(input())
	test = input().split()
	test = [int(ele) for ele in test]
	tests.append(test)

def solve(test):
	max_non = max_con = max_con_temp = test[0]
	for ele in test[1:]:
		max_con_temp = max(max_con_temp + ele, ele)
		max_con = max(max_con_temp, max_con)
		if ele > 0:
			max_non += ele
		max_non = max(max_non, ele)
	print(str(max_con) + ' ' + str(max_non))
for test in tests:
	solve(test)


def maxContiguous(A):
	max_ending_here = max_so_far = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far

def maxNonContiguous(A):
	a = sum([x for x in A if x > 0])
	return max(A) if a == 0 else a
for i in range(int(input())):
	N = int(input())
	A = [int(n) for n in input().split()]
	print(maxContiguous(A), end=' ')
	print(maxNonContiguous(A))


def solve(arr):
	dp = [0] + [arr[0]] * len(arr)
	for i in range(1, len(arr) + 1):
		dp[i] = max(arr[i - 1] + dp[i - 1], arr[i - 1])
	return max(dp)
tcs = int(input())
for i in range(tcs):
	nums = int(input())
	arr = list(map(int, input().split(' ')))
	arr2 = [i for i in arr if i > 0]
	if max(arr) < 0:
		print(max(arr), max(arr))
	else:
		print(solve(arr), sum(arr2))


def contiguous_max(arr):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(arr)):
		val = current_sum + arr[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	max_subarray = arr[best_start_index:best_end_index + 1]
	if max_subarray == []:
		return max(arr)
	return sum(max_subarray)

def non_contiguous(arr):
	max1 = 0
	for i in arr:
		if i > 0:
			max1 += i
	if max1 == 0:
		max1 += max(arr)
	return max1
t = input()
for i in range(int(t)):
	n = input()
	ar = []
	ar1 = input().split(' ')
	for i in ar1:
		ar.append(int(i))
	print(contiguous_max(ar), non_contiguous(ar))


def get_raw_input():
	tests_num = int(input())
	tests = []
	for i in range(tests_num):
		length_array = int(input())
		array = list(map(int, input().split(' ')))
		assert length_array == len(array)
		yield array

def calculate_subarray(array):
	max_sum = array[0]
	max_sum_nc = 0 if array[0] < 0 else array[0]
	current_sum = 0 if array[0] < 0 else array[0]
	for i in range(1, len(array)):
		val = current_sum + array[i]
		if val > 0:
			current_sum = val
			if current_sum > max_sum:
				max_sum = current_sum
		else:
			current_sum = 0
			if max_sum < val:
				max_sum = val
		if array[i] > 0:
			max_sum_nc += array[i]
	if max_sum_nc <= 0:
		max_sum_nc = max(array)
	return {'c': max_sum, 'nc': max_sum_nc}

def main():
	for test in get_raw_input():
		res = calculate_subarray(test)
		print('{contiguous} {noncontiguous}'.format(contiguous=res['c'], noncontiguous=res['nc']))
main()


def max_subarray(L):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(L)):
		val = current_sum + L[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return L[best_start_index:best_end_index + 1]

def max_sum(L):
	s = 0
	for n in L:
		if n > 0:
			s += n
	return s
T = int(input())
for t in range(T):
	N = int(input())
	L_raw = input()
	L_s = L_raw.split()
	L = [int(s) for s in L_s]
	M = max(L)
	if M < 0:
		print(M, M)
	else:
		print(sum(max_subarray(L)), max_sum(L))


def max_subrange(x):
	best_sum = 0
	current_sum = 0
	current_index = -1
	best_start_index = -1
	best_end_index = -1
	for i in range(len(x)):
		val = current_sum + x[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return best_sum

def max_subsequ(x):
	max = -10000
	sum = -1
	for e in x:
		if e <= 0 and e > max:
			max = e
		if e > 0:
			sum += e
	if sum > -1:
		return sum + 1
	else:
		return max
T = int(input())
for i in range(T):
	N = int(input())
	l = input().split()
	x = [int(e) for e in l]
	mss = max_subsequ(x)
	msr = max_subrange(x)
	if mss < 0:
		msr = mss
	print('{} {}'.format(msr, mss))


t = int(input())
for _ in range(t):
	n = int(input())
	ar = [int(x) for x in input().split()]
	best_max = current_max = ar[0]
	for x in ar[1:]:
		current_max = max(x, current_max + x)
		best_max = max(best_max, current_max)
	print(best_max, end=' ')
	total = sum((x for x in ar if x > 0))
	if total > 0:
		print(total)
	else:
		print(max(ar))


def max_subarray(A):
	max_ending_here = max_so_far = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far

def max_non_continious_subarray(A):
	max_ending_here = max_so_far = 0
	maximum = -10000
	for x in A:
		maximum = max(x, maximum)
		if x > 0:
			max_ending_here = max(0, max_ending_here + x)
			max_so_far = max(max_so_far, max_ending_here)
	if max_so_far == 0:
		max_so_far = maximum
	return max_so_far
T = int(input())
for i in range(T):
	N = int(input())
	ar = [int(x) for x in input().split(' ', N)]
	print(max_subarray(ar), max_non_continious_subarray(ar))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().strip().split()))
	ans1 = l[:1]
	mx = l[0]
	for k in range(1, n):
		if ans1[-1] >= 0:
			ans1.append(ans1[-1] + l[k])
		else:
			ans1[-1] = l[k]
		mx = max(mx, ans1[-1])
	ans2 = sum([x for x in l if x > 0])
	if ans2 == 0:
		ans2 = max(l)
	print(mx, ans2)


def max_subarray(arr):
	maxi = cont_max = 0
	non_cont_max = 0
	for x in arr:
		maxi = max(0, maxi + x)
		cont_max = max(maxi, cont_max)
		if x > 0:
			non_cont_max += x
	if non_cont_max <= 0:
		non_cont_max = cont_max = max(arr)
	return [cont_max, non_cont_max]
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(number) for number in input().split()]
	print(' '.join([str(x) for x in max_subarray(arr)]))


def non_cont(a):
	c = 0
	counts = False
	for e in a:
		if e >= 0:
			counts = True
			c += e
	if not counts:
		return max(a)
	return c

def con(a):
	total = a[0]
	e = 1
	t = a[0]
	while e < len(a):
		next = a[e]
		if next >= 0:
			if t > 0:
				t += next
			else:
				t = next
		if next < 0:
			if next >= t:
				t = next
			else:
				t += next
		e += 1
		if t > total:
			total = t
	return total
n = int(input())
for i in range(n):
	k = int(input())
	s = input()
	s = s.split(' ')
	a = []
	for c in s:
		a.append(int(c))
	print('%d %d' % (con(a), non_cont(a)))


for T in range(int(input())):
	n = int(input())
	l = input().split()
	for i in range(n):
		l[i] = int(l[i])
	(c, nc) = (0, 0)
	lres = []
	for x in l:
		if nc < nc + x:
			nc += x
		if c + x > 0:
			c += x
			lres.append(c)
		else:
			lres.append(c)
			c = 0
	c = max(lres)
	if c == 0:
		c = max(l)
	if nc == 0:
		nc = max(l)
	print(str(c) + ' ' + str(nc))


def maxSubArray(L):
	currentSum = 0
	currentIndex = -1
	bestSum = 0
	bestStart = -1
	bestEnd = -1
	non_cont_sum = 0
	if allNegative(L):
		ret_list = [max(L), max(L)]
		return ' '.join(map(str, ret_list))
	for i in range(len(L)):
		val = currentSum + L[i]
		if val > 0:
			if currentSum == 0:
				currentIndex = i
			currentSum = val
		else:
			currentSum = 0
		if currentSum > bestSum:
			bestSum = currentSum
			bestStart = currentIndex
			bestEnd = i
	for j in range(len(L)):
		if L[j] > 0:
			non_cont_sum = non_cont_sum + L[j]
	ret_list = [bestSum, non_cont_sum]
	return ' '.join(map(str, ret_list))

def allNegative(L):
	for i in range(len(L)):
		if L[i] > 0:
			return False
	return True
T = int(input())
for i in range(T):
	Size = input()
	numbers = [int(s) for s in input().split(' ')]
	print(maxSubArray(numbers))


def max_subarray(l):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	nc_sum = 0
	for i in range(len(l)):
		if l[i] > 0:
			nc_sum += l[i]
		val = current_sum + l[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	if best_sum == 0:
		best_sum = max(l)
	if nc_sum == 0:
		nc_sum = max(l)
	print(best_sum, nc_sum)
t = int(input())
for test in range(t):
	n = int(input())
	l = [int(x) for x in input().strip().split(' ')]
	max_subarray(l)


cases = int(input())
for case in range(cases):
	input()
	arr = list(map(int, input().split()))
	cmax = csum = arr[0]
	ncmax = 0
	negmax = -10000
	noPos = True
	a = arr.pop(0)
	if a >= 0:
		noPos = False
		ncmax += a
	elif a > negmax:
		negmax = a
	for e in arr:
		if e >= 0:
			noPos = False
			ncmax += e
		else:
			negmax = max(negmax, e)
		csum += e
		csum = max(csum, e)
		cmax = max(cmax, csum)
	if noPos:
		ncmax = negmax
	print(str(cmax) + ' ' + str(ncmax))


T = int(input())
for x in range(T):
	N = int(input())
	nonContiguousSum = 0
	bestContiguousSum = 0
	currentContiguousSum = 0
	allNegative = True
	maxNegative = 0
	L = list(map(int, input().split()))
	for i in range(N):
		if L[i] > 0:
			allNegative = False
			nonContiguousSum += L[i]
		else:
			maxNegative = L[i] if maxNegative == 0 or L[i] > maxNegative else maxNegative
		val = currentContiguousSum + L[i]
		currentContiguousSum = val if val > 0 else 0
		bestContiguousSum = currentContiguousSum if currentContiguousSum > bestContiguousSum else bestContiguousSum
	if allNegative:
		print(maxNegative, maxNegative)
	else:
		print(bestContiguousSum, nonContiguousSum)


T = int(input())
for t in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	posSum = S[0]
	curSum = S[0]
	maxSum = S[0]
	for i in range(1, N):
		curSum = max(S[i], curSum + S[i])
		posSum = max(S[i], posSum, posSum + S[i])
		maxSum = max(maxSum, curSum)
	print(maxSum, posSum)


def findMaximumSumSubArray(L):
	max_global = L[0]
	current_max = L[0]
	for i in range(1, len(L)):
		val = current_max + L[i]
		current_max = max(val, L[i])
		max_global = max(current_max, max_global)
	return max_global
t = int(input())
for i in range(0, t):
	num_elements = int(input())
	str_arr = input().split(' ')
	L = [int(num) for num in str_arr]
	print(findMaximumSumSubArray(L), end=' ')
	L.sort()
	_sum = 0
	for j in range(0, len(L)):
		if L[j] > 0:
			if _sum < 0:
				_sum = 0
			_sum += L[j]
		else:
			_sum = L[j]
	print('{}'.format(_sum))


def main():
	for T in range(int(input())):
		input()
		number = ''
		sum = 0
		max_sum = 0
		ans = 0
		A = [int(x) for x in input().split()]
		if all((x < 0 for x in A)):
			ans = max(A)
			max_sum = ans
		else:
			for number in A:
				sum += number
				max_sum = max(sum, max_sum)
				sum = max(0, sum)
				if number >= 0:
					ans += number
		print(max_sum, ans)
main()


t = int(input())
for _ in range(t):
	_ = int(input())
	arr = list(map(int, input().split()))
	noncontig = 0
	for i in arr:
		if i > 0:
			noncontig += i
	contig = arr[0]
	tmp = arr[0]
	negs = 0
	for i in arr[1:]:
		tmp = max(tmp + i, i)
		contig = max(tmp, contig)
	if noncontig == 0:
		noncontig = max(arr)
	print(contig, noncontig)


def max_subarray(ar):
	cur_sum = 0
	cur_index = 0
	best_sum = 0
	for (i, n) in enumerate(ar):
		val = cur_sum + n
		if val > 0:
			cur_sum = val
			if cur_sum == 0:
				cur_index = i
		else:
			cur_sum = 0
		if cur_sum > best_sum:
			best_sum = cur_sum
	return best_sum
cases = int(input())
for _ in range(cases):
	input()
	ar = [int(i) for i in input().split()]
	sum_positive = sum((i for i in ar if i > 0))
	if sum_positive == 0:
		least_negative = max(ar)
		print(least_negative, least_negative)
	else:
		print(max_subarray(ar), sum_positive)


def maxsubarray(arr):
	maxtill_here = maxsofar = int(arr[0])
	for x in arr[1:]:
		maxtill_here = max(int(x), maxtill_here + int(x))
		maxsofar = max(maxsofar, maxtill_here)
	return maxsofar

def maxsbanc(arr):
	maxsofar = int(arr[0])
	for x in arr[1:]:
		maxsofar = max(int(x), maxsofar, maxsofar + int(x))
	return maxsofar
tot_exmp = int(input())
for x in range(tot_exmp):
	cursz = int(input())
	curarr = input().split()
	ans1 = maxsubarray(curarr)
	ans2 = maxsbanc(curarr)
	print(' '.join((str(ans1), str(ans2))))


def maxContiguousSubarray(arr):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(arr)):
		val = current_sum + arr[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return sum(arr[best_start_index:best_end_index + 1])

def maxSubarray(arr):
	current_sum = 0
	for i in arr:
		if i > 0:
			current_sum += i
	return current_sum
T = int(input())
for i in range(T):
	n = input()
	positive_value = False
	minimum_negative = 0
	arr = [int(x) for x in input().split()]
	for i in arr:
		if i >= 0:
			positive_value = True
		elif i > minimum_negative or minimum_negative == 0:
			minimum_negative = i
	if positive_value:
		print(maxContiguousSubarray(arr), maxSubarray(arr))
	else:
		print(minimum_negative, minimum_negative)


def max_subarray(array):
	maximum = array[0]
	size = len(array)
	pTemp = 0
	nTemp = 0
	posFlag = True
	if array[0] < 0:
		posFlag = False
	for num in array:
		num = int(num)
		if num >= 0 and posFlag:
			pTemp += num
			if pTemp > maximum:
				maximum = pTemp
		elif num >= 0 and (not posFlag):
			if pTemp + nTemp > 0:
				temp = pTemp + nTemp + num
				pTemp = temp
				if pTemp > maximum:
					maximum = pTemp
			else:
				pTemp = num
				if pTemp > maximum:
					maximum = pTemp
			posFlag = True
		elif num < 0 and (not posFlag):
			if num > maximum:
				maximum = num
			nTemp += num
		else:
			if num > maximum:
				maximum = num
			nTemp = num
			posFlag = False
	if pTemp > maximum and pTemp > 0:
		maximum = pTemp
	return maximum

def max_nonContiguous(array):
	size = len(array)
	total = 0
	maximum = array[0]
	for num in array:
		num = int(num)
		if num > maximum:
			maximum = num
		if num > 0:
			total += num
	if total != 0:
		return total
	else:
		return maximum
t = int(input())
for i_t in range(0, t):
	n = int(input())
	nums = []
	nums = input().strip().split()
	for i in range(n):
		nums[i] = int(nums[i])
	a1 = max_subarray(nums)
	a2 = max_nonContiguous(nums)
	print(str(a1) + ' ' + str(a2))


__author__ = 'Filip'

def get_test_cases_count():
	return int(input())

def get_test_case_size():
	return int(input())

def get_test_case():
	return [int(elem) for elem in input().split(sep=' ')]

def solve():
	test_cases_count = get_test_cases_count()
	for i in range(test_cases_count):
		test_case_size = get_test_case_size()
		test_case = get_test_case()
		(contiguous_max, non_contiguous_max) = solve_case(test_case)
		if non_contiguous_max is None:
			present_solution(contiguous_max)
		else:
			present_solution(contiguous_max, non_contiguous_max)

def present_solution(contiguous_max='', non_contiguous_max=''):
	print(str.format('{0} {1}', contiguous_max, non_contiguous_max))

def solve_case(example):
	contiguous_max_sum = -float('inf')
	contiguous_so_far = 0
	non_contiguous_sum = 0
	plus_encountered = False
	maximal_negative = -float('inf')
	for elem in example:
		if elem > 0:
			plus_encountered = True
			non_contiguous_sum += elem
			contiguous_so_far += elem
			if contiguous_so_far > contiguous_max_sum:
				contiguous_max_sum = contiguous_so_far
		else:
			if elem > maximal_negative:
				maximal_negative = elem
			diff = contiguous_so_far + elem
			if diff > 0:
				contiguous_so_far = diff
			else:
				contiguous_so_far = 0
	if plus_encountered:
		return (contiguous_max_sum, non_contiguous_sum)
	else:
		return (maximal_negative, maximal_negative)
solve()


def maxSubArray(L):
	currentSum = L[0]
	currentIndex = -1
	bestSum = L[0]
	for i in range(1, len(L)):
		if currentSum + L[i] > L[i]:
			val = currentSum + L[i]
		else:
			val = L[i]
		if val > -10000:
			if currentSum == -10000:
				currentIndex = i
			currentSum = val
		else:
			currentSum = 0
			currentIndex = -1
		if currentSum > bestSum:
			bestSum = currentSum
	max = -10000
	for i in range(len(L)):
		if max < L[i]:
			max = L[i]
	if bestSum > max:
		return bestSum
	else:
		return max

def maxSubArray1(L):
	sum = L[0]
	for i in range(1, len(L)):
		if sum + L[i] > L[i]:
			val = sum + L[i]
		else:
			val = L[i]
		if val > sum:
			sum = val
	return sum
t = int(input(''))
for i in range(t):
	n = int(input(''))
	numbers = list(map(int, input().split(' ')))
	print('%d %d' % (maxSubArray(numbers), maxSubArray1(numbers)))


test = int(input())
for case in range(test):
	maxNonContigous = 0
	maxContigous = 0
	currsum = 0
	n = int(input())
	integer = list(map(int, input().split()))
	if len(integer) == 1:
		print(integer[0], integer[0])
		continue
	count = 0
	for i in range(n):
		maxContigous = max(maxContigous, currsum)
		if integer[i] > 0:
			maxNonContigous += integer[i]
		if currsum + integer[i] < 0:
			count += 1
			currsum = 0
		else:
			currsum += integer[i]
	maxContigous = max(maxContigous, currsum)
	if count == len(integer):
		print(max(integer), max(integer))
		continue
	print(maxContigous, maxNonContigous)


import re

def maxContiguous(A):
	maxEndingAtIndex = A[0]
	globalMax = A[0]
	for x in A[1:]:
		maxEndingAtIndex = max(x, maxEndingAtIndex + x)
		globalMax = max(maxEndingAtIndex, globalMax)
	return globalMax

def maxSubarray(A):
	res = sum([x for x in A if x > 0])
	if res == 0:
		return max(A)
	else:
		return res
for _ in range(int(input())):
	input()
	A = list(map(int, re.split(' ', input())))
	print(maxContiguous(A), maxSubarray(A))


def maxContiguousSubarray(array):
	current_sum = 0
	max_sum = 0
	max_neg = -10000
	for x in array:
		val = current_sum + x
		if val > 0:
			current_sum = val
		else:
			current_sum = 0
			if x >= max_neg:
				max_neg = x
			elif x > max_neg:
				max_neg = x
		if current_sum > max_sum:
			max_sum = current_sum
	if max_sum > 0:
		return max_sum
	else:
		return max_neg

def maxNoncontiguousSubarray(array):
	current_sum = 0
	max_neg = 1
	for x in array:
		if x > 0:
			current_sum += x
		elif max_neg == 1:
			max_neg = x
		elif max_neg < x:
			max_neg = x
	if current_sum == 0:
		return max_neg
	else:
		return current_sum
N = int(input())
for i in range(N):
	len = int(input())
	inputArr = [int(x) for x in input().split()]
	print('%d %d' % (maxContiguousSubarray(inputArr), maxNoncontiguousSubarray(inputArr)))


import os, sys, itertools
for _ in range(int(input())):
	(n, xsum) = (int(input()), 0)
	(sum1, sum2, maxv) = (0, 0, -sys.maxsize - 1)
	for i in map(int, input().split()):
		xsum = max(xsum + i, 0)
		sum1 = max(sum1, xsum)
		sum2 = sum2 + max(i, 0)
		maxv = max(maxv, i)
	if sum2 > 0:
		print('%d %d' % (sum1, sum2))
	else:
		print('%d %d' % (maxv, maxv))


def kadane(A):
	max_so_far = max_ending_here = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	return max_so_far
T = int(input())
for test in range(T):
	N = int(input())
	a = [int(i) for i in input().split()]
	s1 = kadane(a)
	if max(a) >= 0:
		s2 = sum([i for i in a if i > 0])
	else:
		s2 = max(a)
	print(s1, s2)


def max_subarray(arr):
	min_cumsum = 0
	max_sub = float('-inf')
	cumsum = 0
	for val in arr:
		cumsum += val
		max_sub = max(cumsum - min_cumsum, max_sub)
		min_cumsum = min(cumsum, min_cumsum)
	return max_sub

def max_subarray2(arr):
	pos = [el for el in arr if el > 0]
	if pos:
		return sum(pos)
	else:
		return max(arr)

def run_case():
	n = int(input())
	arr = [int(s) for s in input().split()]
	assert len(arr) == n
	print(max_subarray(arr), max_subarray2(arr))
for _ in range(int(input())):
	run_case()


num_cases = int(input())
for i in range(num_cases):
	num_int = int(input())
	given_list = input().split(' ')
	given_list = [int(x) for x in given_list]
	highest_continuous = 0
	non_continuous = 0
	smallest_negative = 0
	max_ending = 0
	max_so_far = 0
	for num in given_list:
		max_ending = max(0, max_ending + num)
		max_so_far = max(max_so_far, max_ending)
	highest_continuous = max_so_far
	for num in given_list:
		if num > 0:
			non_continuous = non_continuous + num
	if highest_continuous == 0:
		highest_continuous = max(given_list)
		non_continuous = highest_continuous
	print(str(highest_continuous) + ' ' + str(non_continuous))


__author__ = 'ruben'

def max_subarray(ar):
	max_ending_here = max_so_far = 0
	onlyNegative = True
	for x in ar:
		if x > 0:
			onlyNegative = False
		max_ending_here = max(0, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
	if onlyNegative:
		return (max(ar), max(ar))
	maxsub = 0
	for x in ar:
		if x >= 0:
			maxsub += x
	return (max_so_far, maxsub)
for _ in range(int(input())):
	input()
	ar = list(map(int, input().split(' ')))
	(a, b) = max_subarray(ar)
	print(a, b)


for case in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	m = 0
	currentMax = 0
	for i in range(len(A)):
		currentMax += A[i]
		if currentMax < 0:
			currentMax = 0
		if m < currentMax:
			m = currentMax
	if m == 0:
		print(max(A), max(A))
	else:
		print(m, sum((x for x in A if x > 0)))


T = int(input())
for i in range(0, T):
	N = int(input())
	num_list = list(map(int, input().split()))
	max_num = num_list[0]
	sum_contiguous = 0
	max_sum_contiguous = 0
	sum_noncontiguous = 0
	for num in num_list:
		if num > max_num:
			max_num = num
		sum_contiguous += num
		if sum_contiguous < 0:
			sum_contiguous = 0
		if sum_contiguous > max_sum_contiguous:
			max_sum_contiguous = sum_contiguous
		if num > 0:
			sum_noncontiguous += num
	if max_num < 0:
		print(max_num, max_num)
	else:
		print(max_sum_contiguous, sum_noncontiguous)


def maxSubarray(A):
	total = 0
	maxVal = -999999999999
	for a in A:
		maxVal = max(maxVal, a)
		if a > 0:
			total += a
	if maxVal < 0:
		return maxVal
	else:
		return total

def kadane(A):
	maxSoFar = 0
	maxEndingHere = 0
	maxVal = -99999999999
	for a in A:
		maxEndingHere = max(0, maxEndingHere + a)
		maxSoFar = max(maxSoFar, maxEndingHere)
		maxVal = max(maxVal, a)
	if maxVal < 0:
		return maxVal
	else:
		return maxSoFar
numCases = int(input())
for _ in range(numCases):
	_ = input()
	arr = [int(x) for x in input().split()]
	print(str(kadane(arr)) + ' ' + str(maxSubarray(arr)))


MINIMUM = -10 ** 4

def max_subarray(array):
	current_max = MINIMUM - 1
	abs_max = MINIMUM - 1
	current_best_start = -1
	abs_best_start = -1
	abs_best_end = -1
	for i in range(len(array)):
		if current_max < 0:
			current_max = array[i]
			current_best_start = i
		else:
			current_max += array[i]
		if current_max > abs_max:
			abs_max = current_max
			abs_best_start = current_best_start
			abs_best_end = i
	return sum(array[abs_best_start:abs_best_end + 1])

def sum_positive(array):
	maximum = MINIMUM - 1
	total = 0
	for i in range(len(array)):
		if array[i] > maximum:
			maximum = array[i]
		if array[i] > 0:
			total += array[i]
	if maximum < 0:
		return maximum
	return total
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	print(str(max_subarray(A)) + ' ' + str(sum_positive(A)))


def main():
	ncases = int(input())
	for case in range(ncases):
		length = int(input())
		seq = [int(fld) for fld in input().split()]
		assert length == len(seq)
		print('{} {}'.format(*solvecase(seq)))

def solvecase(seq):
	lo = max(seq)
	if lo <= 0:
		return (lo, lo)
	leastcs = curcs = 0
	bestsum = 0
	for x in seq:
		curcs += x
		if curcs < leastcs:
			leastcs = curcs
		else:
			bestsum = max(bestsum, curcs - leastcs)
	return (bestsum, sum((x for x in seq if x > 0)))
main()


import sys
case_count = int(input())
cases = [[] for _ in range(case_count)]
for i in range(case_count):
	count = int(input())
	s = input().split()
	cases[i] = [int(n) for n in s]
for case in cases:
	positive_sum = 0
	for i in case:
		if i > 0:
			positive_sum += i
	if positive_sum == 0:
		positive_sum = case[0]
		for i in case:
			if i > positive_sum:
				positive_sum = i
	contiguous_sum = -sys.maxsize
	previous_sum = 0
	for i in case:
		if previous_sum > 0:
			previous_sum += i
		else:
			previous_sum = i
		if previous_sum > contiguous_sum:
			contiguous_sum = previous_sum
	print(str(contiguous_sum) + ' ' + str(positive_sum))


def max_sub_sum(L):
	sum = 0
	for i in range(len(L)):
		if L[i] > 0:
			sum += L[i]
	return sum if sum != 0 else max(L)

def max_continuous_sub_sum(L):
	current_sum = 0
	best_sum = 0
	for i in range(len(L)):
		val = current_sum + L[i]
		if val > 0:
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
	return best_sum if best_sum != 0 else max(L)
T = int(input())
for i in range(T):
	size = int(input())
	muh_list = [int(x) for x in input().split()]
	print(str(max_continuous_sub_sum(muh_list)) + ' ' + str(max_sub_sum(muh_list)))


def max_subarray(L):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(L)):
		val = current_sum + L[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return L[best_start_index:best_end_index + 1]
T = int(input())
for _ in range(T):
	l = int(input())
	arr = [int(i) for i in input().split()]
	b = 0
	for i in arr:
		if i > 0:
			b += i
	r = max_subarray(arr)
	a = sum(r)
	if not len(r):
		a = max(arr)
		b = a
	print(a, b)


def max_contiguous_subarray(A):
	sums = []
	max_contigs = []
	for (i, a) in enumerate(A):
		if i == 0:
			max_contigs.append(a)
		else:
			max_contigs.append(max(a, a + max_contigs[i - 1]))
	return max(max_contigs)

def max_subarray(A):
	no_negs = [a for a in A if a >= 0]
	if len(no_negs) == 0:
		return max(A)
	else:
		return sum(no_negs)
T = int(input())
for t in range(0, T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	print(str(max_contiguous_subarray(A)) + ' ' + str(max_subarray(A)))


def maxSubArray(A):
	maxsofar = A[0]
	currmax = A[0]
	plusmax = max(0, A[0])
	for i in range(1, len(A)):
		currmax = max(A[i], currmax + A[i])
		maxsofar = max(currmax, maxsofar)
		plusmax += max(0, A[i])
	print(maxsofar, maxsofar if plusmax == 0 else plusmax)
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	maxSubArray(A)


T = int(input())
for i in range(0, T):
	input()
	line = input()
	t = [int(n) for n in line.split()]
	maxsum = 0
	curmax = 0
	for a in t:
		if curmax + a > 0:
			curmax = curmax + a
		else:
			curmax = 0
		if curmax > maxsum:
			maxsum = curmax
	if maxsum == 0:
		maxsum = -99999
		for a in t:
			maxsum = max(maxsum, a)
	print(maxsum, end=' ')
	if maxsum > 0:
		maxsum = 0
	for a in t:
		if a > 0:
			if maxsum < 0:
				maxsum = a
			else:
				maxsum += a
	print(maxsum)


import sys
srl = sys.stdin.readline

def max_contiguous_subarray(a):
	current_sum = 0
	best_sum = 0
	for i in a:
		val = current_sum + i
		if val > 0:
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
	if best_sum == 0:
		best_sum = max(a)
	return best_sum

def max_noncontiguous_subarray(a):
	best_sum = 0
	for i in a:
		if i > 0:
			best_sum += i
	if best_sum == 0:
		best_sum = max(a)
	return best_sum
T = int(srl().strip())
for case in range(1, T + 1):
	N = int(srl().strip())
	a = [int(num) for num in srl().strip().split(' ')]
	print(max_contiguous_subarray(a), max_noncontiguous_subarray(a))


import sys
T = int(input())
for i in range(T):
	size = int(input())
	allValues = [int(i) for i in input().split()]
	ordered = allValues[:]
	ordered.sort(reverse=True)
	total = 0
	temp = []
	mayorNoCon = ordered[0]
	mayorCon = ordered[0]
	for value in ordered[1:]:
		if value <= 0:
			break
		mayorNoCon = mayorNoCon + value
	for value in allValues:
		total = total + value
		if total < 0:
			total = 0
		if total > mayorCon and total != 0:
			mayorCon = total
	sys.stdout.write(str(mayorCon) + ' ' + str(mayorNoCon) + '\n')


def max_contiguous_sum(array):
	max_sum = -10 ** 10
	current = 0
	for number in array:
		current += number
		if current > max_sum:
			max_sum = current
		if current < 0:
			current = 0
	return max_sum
for _ in range(int(input())):
	n = int(input())
	numbers = [int(x) for x in input().strip().split()]
	positives = [x for x in numbers if x >= 0]
	if len(positives) == 0:
		non_contiguous_sum = max(numbers)
	else:
		non_contiguous_sum = sum(positives)
	print(max_contiguous_sum(numbers), non_contiguous_sum)


def allNegative(L):
	for val in L:
		if val > 0:
			return False
	return True

def maxSubarray(L):
	currentSum = bestSum = 0
	for i in range(len(L)):
		val = currentSum + L[i]
		if val > 0:
			currentSum = val
		else:
			currentSum = 0
		if currentSum > bestSum:
			bestSum = currentSum
	return bestSum

def maxAll(L):
	sum = 0
	for val in L:
		if val > 0:
			sum += val
	return sum
for _ in range(int(input())):
	input()
	A = list(map(int, input().split()))
	if allNegative(A):
		print(max(A), max(A))
	else:
		print(maxSubarray(A), maxAll(A))


def maxContSubArr(L):
	maxSoFar = max(L)
	maxEndingHere = L[0]
	for e in L[1:]:
		maxEndingHere = max([maxEndingHere + e, e])
		maxSoFar = max([maxSoFar, maxEndingHere])
	return maxSoFar

def maxContSubArrBrute(L):
	maxSoFar = L[0]
	for i in range(len(L)):
		sumPrev = 0
		for j in range(i, len(L)):
			sumPrev = sumPrev + L[j]
			if sumPrev > maxSoFar:
				maxSoFar = sumPrev
	return maxSoFar

def maxNonContSubArr(L):
	ret = sum([x for x in L if x > 0])
	if ret <= 0:
		return max(L)
	else:
		return ret
T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	print(maxContSubArr(L), maxNonContSubArr(L))


def max_subarray(arr):
	max_noncontig = max_ending_here = max_so_far = arr[0]
	for x in arr[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_noncontig = max(x, max_noncontig + x, max_noncontig)
		max_so_far = max(max_ending_here, max_so_far)
	return (max_so_far, max_noncontig)
number_of_cases = int(input())
for _ in range(number_of_cases):
	input()
	out = max_subarray(list(map(int, input().split())))
	print(out[0], out[1], sep=' ', end='\n')


def max_subarray_sum(ip):
	max_ending_here = max_so_far = max_non_contig = 0
	for x in ip:
		max_ending_here = max(0, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
		max_non_contig = max(max_non_contig, max_non_contig + x)
	if max_so_far == 0 and 0 not in ip:
		max_so_far = max(ip)
	if max_non_contig == 0 and 0 not in ip:
		max_non_contig = max(ip)
	return (max_so_far, max_non_contig)
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	ip = [int(x) for x in input().strip().split()]
	assert n == len(ip)
	if n > 0:
		(contig, non_contig) = max_subarray_sum(ip)
		print(contig, non_contig)


def max_subarray(L):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(L)):
		val = current_sum + L[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	total = sum(L[best_start_index:best_end_index + 1])
	if total == 0:
		total = get_largest_negative(L)
	return total

def get_largest_negative(L):
	number = L[0]
	for j in range(len(L)):
		if L[j] > number:
			number = L[j]
	return number

def max_number(L):
	num = 0
	for i in range(len(L)):
		if L[i] > 0:
			num += L[i]
	if num == 0:
		num = get_largest_negative(L)
	return num
t = int(input())
for x in range(t):
	length = int(input())
	arr = input().split(' ')
	if length > 1:
		arr = [int(i) for i in arr]
		print(str(max_subarray(arr)) + ' ' + str(max_number(arr)))
	else:
		print(arr[0] + ' ' + arr[0])


def max_sum(array):
	largest_including = largest_overall = array[0]
	non_negative = array[0]
	for x in array[1:]:
		largest_including = max(x, largest_including + x)
		largest_overall = max(largest_including, largest_overall)
		if non_negative >= 0:
			non_negative = max(non_negative, non_negative + x)
		else:
			non_negative = max(non_negative, x)
	return [largest_overall, non_negative]
num_cases = int(input())
for current_case in range(1, num_cases + 1):
	length = int(input())
	array = [int(x) for x in input().split()]
	answer = max_sum(array)
	print('{} {}'.format(*answer))


def max_noncontinous(l):
	temp = 0
	for i in l:
		if temp + i > temp:
			temp += i
	return temp

def max_continous(l):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(l)):
		val = current_sum + l[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return sum(l[best_start_index:best_end_index + 1])
max_non = 0
max_con = 0
t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	flag = False
	count = 0
	for i in range(len(li)):
		count += 1
		if li[i] > 0:
			break
	if count == len(li):
		flag = True
	if flag:
		print(max(li), max(li))
	else:
		max_non = max_noncontinous(li)
		max_con = max_continous(li)
		print(max_con, max_non)


import sys

def maximum_contiguous_subarray(seq):
	max_ending_here = best_so_far = seq[0]
	for number in seq[1:]:
		max_ending_here = max(number, max_ending_here + number)
		best_so_far = max(best_so_far, max_ending_here)
	return best_so_far

def maximum_non_contiguous_subarray(seq):
	positives = [x for x in seq if x > 0]
	if positives:
		return sum(positives)
	else:
		return max(seq)
ncases = int(sys.stdin.readline())
for ncase_index in range(ncases):
	size = int(sys.stdin.readline())
	sequence = [int(x) for x in sys.stdin.readline().split()]
	assert len(sequence) == size
	print(maximum_contiguous_subarray(sequence), end=' ')
	print(maximum_non_contiguous_subarray(sequence))


def nonmaxsum(num):
	s = 0
	for n in num:
		if n > 0:
			s += n
	if s == 0:
		g = -100000
		for n in num:
			g = max(g, n)
		return g
	else:
		return s

def conmaxsum(num):
	e = m = num[0]
	for n in num[1:]:
		e = max(n, e + n)
		m = max(m, e)
	return m
for t in range(int(input())):
	c = int(input())
	n = list(map(int, input().strip().split(' ')))[0:c]
	print(conmaxsum(n), nonmaxsum(n))


T = int(input())
for t in range(T):
	N = int(input())
	a = [int(x) for x in input().split()]
	ans1 = a[0]
	ans2 = 0
	cnt = 0
	for i in range(N):
		cnt += a[i]
		ans1 = max(ans1, cnt)
		if a[i] > 0:
			ans2 += a[i]
		if cnt < 0:
			cnt = 0
	if ans2 == 0:
		ans2 = a[0]
		for i in range(N):
			ans2 = max(ans2, a[i])
	print(ans1, ans2)


t = int(input())
for i in range(0, t):
	smallestneg = -9999999999999999999999999
	maxoverall = -1
	tmp = int(input())
	numbers = str(input()).split()
	maxxx = int(numbers[0])
	currentmax = 0
	for j in range(0, len(numbers)):
		if int(numbers[j]) < 0 and int(numbers[j]) < smallestneg:
			smallestneg = int(number[j])
		currentmax = currentmax + int(numbers[j])
		if currentmax > maxxx:
			maxxx = currentmax
		if currentmax < 0:
			currentmax = 0
		if int(numbers[j]) > 0:
			if maxoverall == -1:
				maxoverall = 0 + int(numbers[j])
			else:
				maxoverall = maxoverall + int(numbers[j])
	if maxoverall == -1:
		maxoverall = maxxx
	print(str(maxxx) + ' ' + str(maxoverall))


import sys

def max_subarray(arr):
	current_sum = 0
	current_start_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	sum_pos_elems = 0
	pos_vals = list(filter(lambda x: x > 0, arr))
	if len(pos_vals) == 0:
		return (max(arr), max(arr))
	for i in range(len(arr)):
		if arr[i] > 0:
			sum_pos_elems += arr[i]
		sum_to_compare = current_sum + arr[i]
		if sum_to_compare > 0:
			if current_sum == 0:
				current_start_index = i
			current_sum = sum_to_compare
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_start_index
			best_end_index = i
	return (sum(arr[best_start_index:best_end_index + 1]), sum_pos_elems)
data = sys.stdin.readlines()
num_cases = int(data[0])
for i in range(0, num_cases):
	arr = list(map(int, data[2 + 2 * i].split(' ')))
	res = max_subarray(arr)
	print(res[0], res[1])


def max_subarray(array):
	current_sum = 0
	current_inedx = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(0, len(array)):
		val = current_sum + array[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	return array[best_start_index:best_end_index + 1]
T = int(input())
for _ in range(0, T):
	N = int(input())
	ar = [int(i) for i in input().split()]
	nc = sum([i for i in ar if i > 0])
	if nc == 0:
		largest_negative = sorted(ar)[-1]
		print(largest_negative, largest_negative)
	else:
		c = sum(max_subarray(ar))
		print(c, nc)


def max_subarray(L):
	current_sum = 0
	current_index = -1
	best_sum = 0
	best_start_index = -1
	best_end_index = -1
	for i in range(len(L)):
		val = current_sum + L[i]
		if val > 0:
			if current_sum == 0:
				current_index = i
			current_sum = val
		else:
			current_sum = 0
		if current_sum > best_sum:
			best_sum = current_sum
			best_start_index = current_index
			best_end_index = i
	if best_start_index > -1:
		return L[best_start_index:best_end_index + 1]
	else:
		return [max(L)]
for _ in range(int(input())):
	numberCount = int(input())
	numbers = [int(x) for x in input().split(' ')]
	contiguousSum = sum(max_subarray(numbers))
	positiveNumbers = [x for x in numbers if x > 0]
	if positiveNumbers:
		nonContiguousSum = sum(positiveNumbers)
	else:
		nonContiguousSum = max(numbers)
	print('{} {}'.format(contiguousSum, nonContiguousSum))


def non_cgous(N, A):
	min_pos = A[0]
	total = min_pos
	for i in range(1, N):
		if min_pos < 0 and A[i] > min_pos:
			min_pos = A[i]
			total = min_pos
		elif A[i] > 0:
			total += A[i]
	return total

def cgous(N, A, s, e):
	max_upmost = A[0]
	max_end_here = A[0]
	for i in range(1, N):
		max_end_here = max(A[i], max_end_here + A[i])
		max_upmost = max(max_upmost, max_end_here)
	return max_upmost
T = int(input())
for i in range(0, T):
	N = int(input())
	A = input().split()
	for j in range(0, N):
		A[j] = int(A[j])
	c_max = -999999
	print(str(cgous(N, A, 0, N)) + ' ' + str(non_cgous(N, A)))


def max_noncont(arr):
	rmax = arr[0]
	rsum = 0
	rhit = False
	for el in arr:
		if el >= 0:
			rsum += el
			rhit = True
		rmax = max(el, rmax)
	return rsum if rhit else rmax

def max_cont(arr):
	emaxh = arr[0]
	emaxs = arr[0]
	for el in arr[1:]:
		emaxh = max(el, emaxh + el)
		emaxs = max(emaxs, emaxh)
	return emaxs
t = int(input())
for _ in range(t):
	els = int(input())
	arr = list(map(int, input().split()))
	print('%s %s' % (max_cont(arr), max_noncont(arr)))


def max_subarray(A):
	positive_sum = 0
	if A[0] > 0:
		positive_sum = A[0]
	largest_num = A[0]
	max_ending_here = max_so_far = A[0]
	for x in A[1:]:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
		if x > largest_num:
			largest_num = x
		if x > 0:
			positive_sum += x
	if largest_num < 0:
		non_contingent_sum = largest_num
	else:
		non_contingent_sum = positive_sum
	return (max_so_far, non_contingent_sum)
inputs = input()
for i in range(0, int(inputs)):
	input()
	elements = input()
	arr = [int(x) for x in elements.strip().split(' ')]
	(max1, max2) = max_subarray(arr)
	print('{:d} {:d}'.format(max1, max2))


def sum_nc(a):
	if max(a) < 0:
		return max(a)
	sum = 0
	for i in range(len(a)):
		if a[i] > 0:
			sum = sum + a[i]
	return sum

def sum_c(a):
	if max(a) < 0:
		return max(a)
	crm = a[0]
	msf = a[0]
	i = 1
	while i < len(a):
		crm = max(a[i], crm + a[i])
		msf = max(crm, msf)
		i = i + 1
	return msf
t = int(input())
ar = []
for i in range(t):
	n = int(input())
	ar.append([])
	b = input()
	for j in b.split():
		ar[i].append(int(j))
for i in range(t):
	print(sum_c(ar[i]), sum_nc(ar[i]))