📌 문제

위와 같이 주식가격이 변할 때, 가장 큰 이익을 낼 수 있는 값을 구하라.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

📌 아이디어

단순히 최대값과 최소값만 찾으면 되는거 아닌가? 라고 간단하게 생각할 수 있다. 그러나 위 문제는 index가 시간을 나타내기 떄문에 단순 최소 최대구하는 것으로 문제를 풀 수 없다.

위의 그림에서도 배열의 최소값과 저점매수 지점이 일치하지 않는 것을 알 수 있다.

즉, 주식가격이 시간에 따라 앞으로 나아가는 형태이므로

( 전의 최대값에서 앞의 최소값을 뺄 수 없다 )

1. 최소값의 갱신

2. 최대-최소의 차이 갱신

두가지를 해주어야 한다.

profit = 0
min_value = 9999999 ( sys.maximize )

for i in arr:
    min_value = min(min_value,i)
    profit = max(profit, i - min_value )