#1094 부분 수열의 최대값

106  1 s   128 MB  

Description

{ -1, 2, 5, -3, 9, 8, -4, -5, 10, -11 } 의 수열이 있을 때, 이 수열의 모든 원소의 합을 구하면 10이다.

하지만 2번째 원소부터, 9번째 원소까지의 합을 구하면 22로 이 수열의 경우 2번째부터 9번째까지의 부분수열이 이 수열의 최대 부분수열이 된다.

N개의 원소로 이루어진 수열을 입력받았을 때 이 수열의 부분 수열중 합이 최대가 되는 부분수열을 구하는 프로그램을 작성하라.

 

Input

맨 처음 테스트 케이스의 갯수 T(1 <= T <= 100)를 입력받는다. 그 뒤에 T의 갯수만큼 원소의 개수 N을 입력받고 N개의 원소 e[i]를 입력받는다. (3 <= N <= 500, -1000 <= e[i] <= 1000)

Output

각 테스트 케이스마다 수열의 부분 수열중 합이 최대가 되는 부분수열을 구하여 시작점과 끝점 및 부분수열의 합을 출력한다.

(스페셜 저지 적용)

Sample Input

Sample Output

3
4
1 -1 1 2
5
1 -2 3 -4 5
10
-1 2 5 -3 9 8 -4 -5 10 -11
3 4 3
5 5 5
2 9 22