[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 상세보기