적도

면접 대비

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

요약

각 테스트 케이스마다 원 위에 놓인 도시의 이익이 주어지며 가장 이익이 큰 연속 구간을 구하고 모두 손실이면 0을 출력합니다.

문제

도시들이 한 바퀴로 늘어선 행성 적도에서, 한 방향으로 연속된 구간만 털 수 있다. 각 도시의 수익(음수면 손실)이 주어질 때 얻을 수 있는 최대 총액을 구하라. 아예 착륙하지 않아 0을 선택할 수도 있다.

첫 줄에 테스트 수 $T$ 가 주어진다. 각 테스트는 도시 수 $n$ 과 $n$ 개의 정수 $c_i$ 로 주어진다.

각 테스트마다 최대 총 수익을 한 줄에 출력한다.

예제 1

입력

3
3 1 2 3
8 4 5 -1 -1 1 -1 -1 5
2 -1 -1

예상 출력

6
14
0