LeetCode/Best Time to Buy and Sell Stock

( 블로그 기사 의 전재)

도쿄도에 거주하는 저입니다만, 혼자 개발 합숙되는 것을 해 보려고 생각하고, 어느 현의 호텔에 묵고, 방에서 나오지 않고 묵묵히 코드의 사경을 하고 있습니다.

그러나, 혼자 개발 합숙은, 자신에 대한 응석을 끊는 정신의 소유자가 아니면, 그다지 적합하지 않네요.
드디어 LeetCode에 바람을 피웠습니다.

다음부터는 코워킹 스페이스에 돌격해 보고 싶습니다.

글쎄, 오늘의 문제.

[ h tps : // / ㅇ t 여기. 코 m / p 로 b ぇ ms / 베 st - 치메 - 브 y - 앙 d - 셋 ls와 ck / ]

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Example 2:

가장 싼 때에 사고, 높은 때에 팔지 않는 것으로, 최대의 이익은 얼마가 되는지 산출하는 문제입니다.
현실에는 앞서의 가격을 알고 있는 것은 드뭅니다만, 상당 정밀도가 높은 시계열 예측 모델이 되어 있으면 완찬? 알고리즘입니까?

해답·해설

해법 1

해법을 생각해내는 것은 어렵지 않다고 생각합니다.
이번 문제는 시간 계산량은 어떻게 열심히 해도 [tex:O(n)]라고 하는 곳이므로 알고리즘의 비교는 하지 않고, 간결한 코드와 이마이치인 코드를 나란히 둡니다.

우선 내 submit 코드.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        if prices:
            buy = prices[0]
            for price in prices[1:]:
                if price < buy:
                    buy = price
                if price - buy > ans:
                    sell = price
                    ans = sell - buy
        return ans

코드의 의미는 매우 간단하고, 구매가 buy는 싼 가격이 있으면 대체, 판매 가격 sell은 이익 ans를 넘는 이익이 나오면 대체한다는 조작을 요소 몇 분 반복하고 있을 뿐입니다.

계속해서 Discussion에서 찾아낸 5 lines solution.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit, min_price = 0, float('inf')
        for price in prices:
            min_price = min(min_price, price)
            profit = price - min_price
            max_profit = max(max_profit, profit)
        return max_profit

코드의 의미는 내 submit 한 것과 동일하지만 매우 간단합니다.
특히, 초기값을 max_profit, min_price = 0, float('inf') (으)로 설정하는 곳이 아직 자신에게는 생각하지 못했습니다.