BOJ 2846, 오르막길

이 문제는, N개의 지형 높이가 주어졌을 때,

오르막길의 최대 높이 차이를 찾는 문제입니다.

해결 방법은 간단합니다.

저는 2가지 변수를 처음과 끝을 가리키는 화살표처럼 사용해 문제를 해결했습니다.

처음에 first와 last는 동일하게 arr[0]입니다.

예제를 통해 진행을 알아볼까요

8
12 20 1 3 4 4 11 1

입력이 다음과 같이 주어집니다.

for문을 통해 다음 원소가, 현재 last가 가리키고 있는 원소보다 크지 않을때까지 진행합니다.

```

1) first = 12, last = 12

 - 12 < 20? TRUE

2) first = 12, last = 20

 - 20 < 1? FALSE

 2-1) answer = max(answer, last-first);

3) first = 1, last = 1

...

...

```

이런식으로 오르막길이 아니게 될 때까지 배열을 순회하면, O(N)의 시간복잡도 안에 문제를 해결할 수 있습니다.