최대 경로 합

면접 대비

시간 제한1초메모리 제한64 MB

요약

간선 가중치 배열에서 합이 가장 큰 연속 구간의 양 끝점을 출력하고 최대합이 양수가 아니면 no good path를 출력합니다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

정점이 일렬로 이어진 그래프가 있다. 정점에는 1번부터 $r$ 번까지 번호가 붙어 있고, $i$ 번 정점과 $i+1$ 번 정점을 잇는 간선의 가중치는 $w_i$ 이다. 가중치는 양수일 수도 있고 음수일 수도 있다.

$i < j$ 일 때 $i$ 번 정점에서 $j$ 번 정점까지 가는 경로의 값은 그 경로가 지나는 간선의 가중치를 모두 더한 값 $w_i + w_{i+1} + \dots + w_{j-1}$ 이다.

값이 가장 큰 경로를 찾는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 $n$ ( $1 \le n \le 100$ )이 주어진다.

각 테스트 케이스는 정점의 개수 $r$ ( $2 \le r \le 50$ )로 시작하고, 이어서 정수 $w_1, w_2, \dots, w_{r-1}$ 이 주어진다. $w_i$ 는 $i$ 번 정점과 $i+1$ 번 정점을 잇는 간선의 가중치이고 $-10000 \le w_i \le 10000$ 이다. 수는 공백이나 줄바꿈으로 구분된다.

출력

각 테스트 케이스마다 한 줄에, 값이 가장 큰 경로의 시작 정점 $i$ 와 끝 정점 $j$ 를 공백으로 구분해 출력한다.

값이 가장 큰 경로가 여러 개면 길이가 가장 긴 것, 즉 $j-i$ 가 가장 큰 것을 고른다. 값과 길이가 모두 같은 경로가 여러 개면 $i$ 가 가장 작은 것을 고른다.

가장 큰 값이 양수가 아니면 no good path를 출력한다.

예제2

예제 1

입력

4
3 -1 6
6 1 -2 1 6 -3
10 4 -5 4 -3 4 4 -4 4 -5
4 -2 -3 -4

예상 출력

2 3
3 5
3 9
no good path

예제 2
입력
```
2
2 5
2 -5
```
예상 출력
```
1 2
no good path
```