최댓값과 최솟값의 차가 최대인 부분수열

면접 대비

시간 제한0.5초메모리 제한256 MB

요약

수열이 주어질 때, 모든 연속 부분 수열 중 최댓값과 최솟값의 차가 가장 큰 경우에 그 길이가 최소인 구간의 길이를 구한다.

난이도: 보통10점 중 5점
유형: 투 포인터, 배열, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

수열의 부분수열이란 그 수열의 연속한 일부 항을 원래 순서대로 나열해 얻을 수 있는 수열을 말한다. (부분수열의 통상적인 정의는 이것과 다르다.) 길이 $N$ 의 수열 $A$ 가 주어질 때, $A$ 의 부분수열 중 (부분수열 내 최댓값) - (부분수열 내 최솟값)이 최대가 되는 것들 가운데 길이가 가장 짧은 부분수열의 길이를 구하여라.

입력

첫 줄에 $N$ 이 주어진다. ( $1 \le N \le 10^5$ )

다음 줄에 $N$ 개의 수가 공백으로 구분되어 주어지며, $i$ 번째 수는 $A_i$ 를 뜻한다. ( $1 \le A_i \le 10^5$ )

출력

문제의 답인 정수를 하나 출력한다.

예제2

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