"""
입력 [7,1,5,3,6,4] => 주식 가격
주식을 사고 팔아서 얻을 수 있는 최대 이득을 리턴해라
7 buy 1 sell -> -6
1 but 6 sell -> 5 (최대 이득)
저점에 사서 고점에 팔아라
입력받은 배열에서 저점을 확인해야 하고 고점을 확인해야 한다.
하지만 단순 최대, 최소값으로는 안됨
왜냐면 시간이 지난 후에는 사거나 팔 수 없기 때문
ex> 아 그때 팔걸, 아 그때 살걸..
list 안에서 포인터가 이동하면서 저점을 갱신하고 최대 이득을 max(최대이득, 현재가격) 으로 계속 갱신함
마지막 까지 남아있는 최대 이득을 리턴함
Constraints:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# prices 의 어떤 price 와 비교해도 price 가 lowest_point 를 대체하도록
# 초기값을 설정 Constraints 0 <= prices[i] <= 10^4 이어서 100000 로 지정함
# 초기값을 None 으로 지정하면 누가 크고, 작은지 비교할 수 없기 때문
lowest_point = 10000
profit = 0
for price in prices:
lowest_point = min(lowest_point, price)
profit = max(profit, price - lowest_point)
return profit
web-developer