package com.yongk.algospot.MAXSUM;

import java.util.Scanner;

public class MAXSUM {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = Integer.parseInt(sc.nextLine());
		while(T-- > 0) {
			int N = sc.nextInt();
			sc.nextLine();
			int[] input = new int[N];
			String[] temp = sc.nextLine().split(" ");
			for (int i = 0; i < N; i++) {
				input[i] = Integer.parseInt(temp[i]);
			}
			System.out.println(getMaximumSetFast(input));
		}
		sc.close();
	}
	private static int getMaximumSetFast(int[] input) {
		int max = 0;
		int from = 0;
		for (int i = 0; i < input.length; i++) {
			from = Math.max(from + input[i], 0);
			max = Math.max(max, from);
		}
		return max;
	}
	private static int getMaximumSetSlow(int[] input) {
		int[] sum = new int[input.length];
		sum[0] = input[0];
		int max = 0;
		for (int i = 1; i < input.length; i++) {
			sum[i] = sum[i - 1] + input[i];
			max = Math.max(max, sum[i]);
		}
		
		for (int i = 0; i < sum.length; i++) {
			for (int j = i; j < sum.length; j++) {
				max = Math.max(max, sum[j] - sum[i]);
			}
		}
		return max;
	}
	

}
