ascode.org discuss3

Problem1227--부분 수열의 최대값

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 88 Solved: 25
[Submit] [Status] [Web Board] [Creator:]

{ -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)

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

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

[Submit] [Status]