공상에 잠긴 주식 중개인

면접 대비

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

요약

일별 주가와 100000주 보유 한도가 주어질 때, 100달러로 시작해 정수 주식만 사고팔아 얻을 수 있는 최대 금액을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

주식 중개인 지나 리드는 오늘따라 일이 한가하다. 솔리테어를 몇 판 돌리는 사이에 지나는 공상에 잠긴다. 미래를 알아맞히는 일은 어렵다. 하지만 과거로 돌아가서 주가 기록을 그대로 알고 있다면 이익을 최대로 불릴 수 있지 않을까?

지나는 이런 상상을 한다. 며칠 전으로 돌아가면서 겨우 $100만 들고 간다면, 세상에서 가장 변동이 심한 주식인 Rollercoaster Inc.를 알맞은 시점에 사고팔아서 얼마나 벌 수 있을까? 테네리페의 저택에서 편하게 은퇴할 만큼 벌 수 있을까?

지나는 주식을 쪼개서 살 수 없고 정수 주 단위로만 산다. Rollercoaster Inc.의 총 주식 수는 100000주이므로 지나는 어느 순간에도 100000주를 넘게 가질 수 없다. 지나의 공상 속 세계는 단순하다. 주식을 사고팔 때 수수료가 없고, 주가는 하루에 한 번만 바뀌며, 지나의 거래는 주가에 영향을 주지 않는다.

입력

첫째 줄에 지나가 공상 속에서 거슬러 올라가는 날짜 수 $d$ ( $1 \le d \le 365$ )가 주어진다. 다음 $d$ 개 줄 중 $i$ 번째 줄에는 $i$ 일째에 지나가 Rollercoaster Inc. 주식 한 주를 사거나 팔 수 있는 가격 $p_i$ ( $1 \le p_i \le 500$ )가 주어진다. 날짜는 오래된 순서대로 주어진다.

출력

마지막 날의 거래까지 마쳤을 때 지나가 가질 수 있는 돈의 최댓값을 출력한다. 가지고 있는 주식은 돈으로 세지 않으므로 마지막 날에는 주식을 모두 팔아 현금으로 바꾼다. 답은 $2^{32}$ 보다 클 수 있다.

예제4

예제 1
입력
```
6
100
200
100
150
125
300
```
예상 출력
```
650
```
예제 2
입력
```
1
100
```
예상 출력
```
100
```
예제 3
입력
```
5
500
400
300
200
1
```
예상 출력
```
100
```
예제 4
입력
```
5
1
2
3
4
5
```
예상 출력
```
500
```