問題
N개의 정수로 구성된 배열 arr[]이 주어진다.
이 배열에서 적어도 1개의 원소를 포함하는
임의의 연속된 구간의 합이 0에 가장 가까운 구간을 찾는 프로그램을 작성해보자.
예를 들어 N이 7인 arr[]이 아래와 같다고 하자.
13, -3, 2, 7, -10, -5, 9
이 경우 -3, 2, 7, -10, -5, 9 구간의 합을 구하면 0이 되므로 0에 가장 가까운 구간이다.
入力
첫 행에 N이 입력된다. ( 1 <= N <= 300,000)
다음 행에 N개의 정수 arr[i]가 공백으로 구분되어 입력된다.
( -1,000,000,000 <= arr[i] <= 1,000,000,000)
[제약사항]
* 전체 데이터에서 20% 에 해당하는 데이터는 1 <= N <= 5,000 이다.
* 전체 데이터에서 20% 에 해당하는 데이터는 5,000 < N <= 50,000 이다.
* 전체 데이터에서 60% 에 해당하는 데이터는 50,000 < N <= 300,000 이다.
出力
첫 행에 합이 0에 가장 가까운 구간의 합을 출력한다.
다음 행에 구간의 시작 인덱스와 끝 인덱스를 공백으로 구분하여 출력한다.
인덱스는 1 ~ N까지이다.
답이 되는 구간이 여러 개인 경우 시작 인덱스가 작은 것을 출력한다.
그래도 같은 경우 끝 인덱스가 작은 것을 출력한다.
例題 #1
7
13 -3 2 7 -10 -5 9
0
2 7
例題 #2
5
4 5 1 2 3
1
3 3
例題 #3
3
-4 -5 8
-1
1 3
出典
comkiwer
ログインしないとコードを書けません。