[파이썬 알고리즘] 7장 - 주식을 사고팔기 가장 좋은 시점

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

Best Time to Buy and Sell Stock - LeetCode

 

<문제>

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.

 

<예시>

Input: [7,1,5,3,6,4]

Output: 5

 

---

코드는 짧은데, 천천히 이해해봐야 할 것 같다.

무작정 가격이 최소인 시점, 최소인 시점 이후의 가격 최대 시점을 구하는 것이 아니라,

시점을 옮겨가면서 그 당시의 가장 최소인 가격과 각 시점에서의 가격의 차이를 구하고

이 값을 maximum과 비교해서 업데이트 하는 방식이다.

 

 

# my solution (아래 코드보다 비효율)
def max_profit_1(prices: List[int]) -> int:
    max_profit = 0
    for i, buy_price in enumerate(prices[:-1]):
        sell_price = max(prices[i+1:])  # buy 시점 이후의 가격 중 MAX
        max_profit = max(max_profit, sell_price-buy_price)
    return max_profit


# 저점과 현재 값과의 차이 계산
# 이해하자! 이해하자!
def max_profit_2(prices: List[int]) -> int:
    max_profit = 0  # max_profit = -sys.maxsize
    buy_price = sys.maxsize

    for price in prices:
        buy_price = min(price, buy_price)
        max_profit = max(max_profit, price-buy_price)
    return max_profit