문제1227--부분 수열의 최대값

1227: 부분 수열의 최대값

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 80  통과: 22
[제출] [채점기록] [묻고답하기] [만든사람:]

문제 설명

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

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

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



 

입력 설명

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

출력 설명

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

입력 예시 Copy 

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

출력 예시 Copy 

3 4 3
5 5 5
2 9 22

출처/분류

 
[제출] [채점기록]