문제1217--절대치 합계가 가장 큰 구간 찾기

1217: 절대치 합계가 가장 큰 구간 찾기

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

N개의 정수가 주어집니다. 절대치 합계가 가장 큰 연속된 부분 구간을 찾아주세요. 이 구간의 크기는 최소 1이상이어야 합니다.

입력 설명

첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스마다 첫 줄에는 나열되는 정수의 개수 N(1<=N<=10,000)이 주어집니다. 그다음 줄에는 정수 K(-105<=K<=105)가 주어집니다. 

입력 예시 Copy

2
6
2 -5 1 -4 3 -2
1
-1000

출력 예시 Copy

8
1000

도움

2 -5 1 -4 3 -2가 있을 때 첫 3개 요소로 구성된 구간의 합은 2+(-5)+1 = -2가 되는데, 이처럼 합계가 음수이면 절대치로 바꾸어 고려해야 합니다. 해당 예제에서 -5 1 -4 구간의 합계가 -8입니다. 그것의 절대치가 8이기 때문에 해당 문제에서 가장 큰 절대치 합계가 됩니다.

출처/분류