В поисках максимальной суммы

시간 제한3초메모리 제한1024 MB

요약

양 끝값이 같은 비어 있지 않은 부분배열 중 합이 최대인 것을 찾아 합과 구간의 양 끝을 출력한다.

난이도: 보통10점 중 5점
유형: 누적 합, 해시맵, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

Мама подарила маленькой девочке Алёне массив чисел. Девочку заинтересовали непрерывные подмассивы с равными числами на концах. Среди таких подмассивов ненулевой длины Алёна хочет найти подмассив с максимальной суммой. Формально говоря, требуется найти такие $1 \leq l \leq r \leq n$ , что $a\_l = a\_r$ и сумма чисел $a\_l + a\_{l+1} + \dots + a\_r$ максимальна.

입력

В первой строке входных данных находится число $n$ ( $1 \leq n \leq 1\\,000\\,000$ ) --- количество чисел в массиве $a$ .

Во второй строке входных данных находятся $n$ целых чисел $a\_1, a\_2, \dots, a\_n$ ( $-10^9 \leq a\_i \leq 10^9$ ).

출력

В первой строке выведите максимальную сумму в подмассиве, удовлетворяющем условию задачи.

Во второй строке выведите 2 целых числа $l$ и $r$ , такие что $1 \leq l \leq r \leq n$ и $a\_l, a\_{l + 1}, \dots, a\_r$ --- искомый подмассив с максимальной суммой.

Если существует несколько ответов, выведете любой из них.

힌트

Обратите внимание, во втором примере все числа отрицательные, но Алёна всё равно должна выбрать какой-то непустой подмассив.

예제3

예제 1
입력
```
5
1 2 1 2 3
```
예상 출력
```
5
2 4
```
예제 2
입력
```
3
-1 -1 -1
```
예상 출력
```
-1
1 1
```
예제 3
입력
```
3
1 2 3
```
예상 출력
```
3
3 3
```