최대 연속 부분합 찾기
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- MAXSUM
- 5000ms
- 65536kb
- 5245
- 1321 (25%)
-
- 출처
- 분류
문제
N개의 정수를 담고 있는 배열 A가 주어졌을 때, 여기서 가능한 연속 부분합을 구하는 프로그램을 작성하라.
여기서 연속 합이라는 것은 배열 A = { a1, a2, ..., aN } 에서 아무 값도 선택을 하지 않거나( 이 경우 합은 0 ), 배열의 임의의 i번째 수 부터 j번째 수 까지( ai, ai+1, ..., aj ) ( 1 <= i <= j <= N )를 합한 값을 뜻한다.
입력
입력의 첫번째 줄에는 테스트 케이스의 개수 T가 입력된다.
그리고 그 다음줄 부터 한줄에 하나씩 T개의 테스트 케이스가 입력된다.
테스트 케이스의 첫번째 줄에는 정수 N(1<=N<=105)가 입력된다.
그리고 그 다음줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 숫자의 범위는 -100이상 100이하의 정수다.
출력
한줄에 하나씩 테스트 케이스의 순서대로 각 테스트케이스에 대한 가장 큰 연속 부분합을 출력한다.
예제 입력
2 4 1 2 3 4 3 -1 0 1
예제 출력
10 1
노트
