반응형
leetcode.com/problems/best-time-to-buy-and-sell-stock/
Best Time to Buy and Sell Stock - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
한 번의 거래로 낼 수 있는 최대 이익을 계산하는 문제.
저점에 사서 고점에 팔아야 최대 수익이 남는데,
저점에서 먼저 산 뒤, 이후 최고점에서의 차액이 가장 커야 한다. 선후관계가 있다는 소리.
카데인 알고리즘을 활용하면 O(n)에 풀어낼 수 있다고 한다.
아래 풀이는 이 책을 참고하였다.
 |
|
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] LeetCode 739. Daily Temperature (0) | 2020.10.24 |
|---|---|
| [Python] LeetCode 234. Palindrome Linked List (0) | 2020.10.23 |
| [Python] LeetCode 238. Product of Array Except self (0) | 2020.10.19 |
| [Python] 프로그래머스. 쿼드압축 후 개수세기 (1) | 2020.10.14 |
| [Python] 프로그래머스. 3진법 뒤집기 (1) | 2020.10.12 |