학원 모의고사 최고 상승 구간

문제

한 학원에서는 N일 동안 매일 모의고사를 치르고, 전날 대비 학원 전체 평균 점수의 변화량을 기록해 두었다. i번째 날의 변화량은 정수 a_i이며, 양수이면 평균이 오른 것이고 음수이면 내린 것이다. 원장은 연속한 날들의 구간 [l, r] (1 ≤ l ≤ r ≤ N)을 하나 골라 그 구간의 변화량을 모두 더한 값 a_l + a_{l+1} + … + a_r 을 그 구간의 상승 폭이라고 부른다. 구간은 최소 하루 이상이어야 하므로 모든 변화량이 음수여도 반드시 하나는 골라야 한다. 원장이 알고 싶은 것은 상승 폭이 가장 큰 구간의 상승 폭이다. 상승 폭이 최대인 구간이 여러 개이면 그중 길이(r - l + 1)가 가장 짧은 구간을 기준으로 삼는다. 이 가장 큰 상승 폭과, 그 상승 폭을 만드는 구간 중 가장 짧은 구간의 길이를 구하는 프로그램을 작성하라. 구간을 반으로 나누어 왼쪽, 오른쪽, 가운데를 가로지르는 경우를 합치는 분할 정복으로 풀 수 있다.

입력

첫째 줄에 N이 주어진다. 둘째 줄에 a_1, a_2, …, a_N이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, |a_i| ≤ 10^9 이며 모든 값은 정수이다.

출력

한 줄에 가장 큰 상승 폭과 그 상승 폭을 만드는 가장 짧은 구간의 길이를 공백으로 구분해 출력한다.

5
-2 3 -1 4 -5

6 3

3
-5 -2 -7

-2 1

4
3 0 -3 3

3 1

출처: Devin.KR 자체 제작