최대 상승

면접 대비

시간 제한1초메모리 제한512 MB

요약

날마다의 주가가 주어졌을 때 한 번 사고 그 이후 날에 한 번 팔아 얻을 수 있는 최대 이익을 구합니다.

난이도: 쉬움10점 중 3점
유형: 배열, 그리디
정답자: 아직 제출이 없습니다

문제

미래를 예측하는 능력이 있는 정균이는 앞으로 $N$ 일간 ANA 회사의 주가가 어떻게 변할지 정확히 예측할 수 있다. 정균이는 예측한 결과를 바탕으로 ANA 회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 최대한의 이득을 얻으려고 한다.

ANA 회사의 앞으로 $N$ 일간의 주가를 $a_1, a_2, ..., a_N$ 이라고 하자. 정균이가 $i$ 번째 날에 주식을 사고 $j$ 번째 날에 판다면 $a_j - a_i$ 만큼의 이득을 얻을 수 있다. 정균이는 자금이 넉넉하기 때문에 주가가 아무리 높아도 주식을 살 수 있고, 상황이 여의치 않으면 사자마자 바로 팔 수도 있다.

앞으로 $N$ 일간 ANA 회사의 주가가 주어졌을 때, 정균이가 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득은 얼마인가?

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 200000$ )이 주어진다.

두 번째 줄에 정수 $a_1, a_2, ..., a_N$ 이 주어진다. $a_i$ ( $1 \le a_i \le 10^9$ )는 $i$ 번째 날의 ANA 회사의 주가이다.

출력

ANA 회사의 주식 한 주를 적당한 시점에 사고 적당한 시점에 팔아서 얻을 수 있는 최대 이득을 출력한다.

예제3

예제 1
입력
```
5
4 2 3 1 5
```
예상 출력
```
4
```
예제 2
입력
```
3
3 2 1
```
예상 출력
```
0
```
예제 3
입력
```
4
7 1 2 6
```
예상 출력
```
5
```