[Python] LeetCode 121. Best time to buy and sell stock

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

Best Time to Buy and Sell Stock - LeetCode

한 번의 거래로 낼 수 있는 최대 이익을 계산하는 문제.

저점에 사서 고점에 팔아야 최대 수익이 남는데,

저점에서 먼저 산 뒤, 이후 최고점에서의 차액이 가장 커야 한다. 선후관계가 있다는 소리.

 

카데인 알고리즘을 활용하면 O(n)에 풀어낼 수 있다고 한다.

아래 풀이는 이 책을 참고하였다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

 

 

	import math
	class Solution:
	def maxProfit(self, prices: List[int]) -> int:
	# 최솟값을 매번 갱신하면서
	# 현재 값과 최솟값과의 차이를 구해 최댓값을 저장하도로 한다
	# 카데인(Kadane) 알고리즘으로, O(n) 에 풀이 가능
	profit = 0
	min_price = math.inf
	for price in prices:
	min_price = min(price, min_price)
	profit = max(profit, price - min_price)
	return profit

view raw [Leetcode] best time to buy and sell stock.py hosted with ❤ by GitHub