최대 부분 배열 합

크기 $N$인 정수 배열 $X$가 주어질 때, 연속한 부분 배열 중 원소 합이 최대인 값을 구한다. 즉 $\max_{1 \le i \le j \le N} (X[i] + \cdots + X[j])$를 계산한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스는 배열 크기 N$$(1 \le N \le 1000) 한 줄과, 다음 줄에 $|X_i| < 1000$을 만족하는 $N$개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 maximum subarray의 합을 한 줄에 출력한다.