✓[LeetCode] 121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

 

Constraints:

  ▷ 1 <= prices.length <= 105

  ▷ 0 <= prices[i] <= 104

 

Example:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

 

 그래도 다행인거 조금 비슷한 접근을 하였다. min_val에 가장 작은 값을 넣어 놓고, 그 값의 인덱스를 가져와 그 위치부터 끝가지 위치중에 가장 큰 값을 골라 max_val에 넣어 두고.. 두 값을 뺀 것이 정답이라고 생각했다. 다른 식으로 변형해도 이 방법빼곤 생각나지 않았다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
            
        min_val = min(prices)
        max_val = 0
        
        for i in range(prices.index(min_val), len(prices)-1):

            if prices[i] > max_val:
                max_val = prices[i]
        
        return max_val - min_val

 

 책에서는 profit은 0 이상일테니 초기값을 0으로 설정, min_price는 시스템에서 가장 큰 값으로 설정해서 다음 값이랑 비교하면 무조건 값이 바뀌게 설정했다. 그리고 prices 배열을 하나씩 순회하면서 min_price를 최신화하고 기존의 profit이랑 현재 값에서 제일 작은 값 뺀 값이랑 비교해 더 큰 profit으로 최신화한다. 그리고 그 profit을 리턴해준다.

 

 글로만 보면 조금 헷갈리는데.. 직접 적어서 값이 변하는 걸 보면 직관적으로 이해되는 것 같다. min_price는 반복문을 돌면서 가장 작은 값으로 계속 업데이트 해주고, profit도 반복문을 순회하면서 가장 큰 값이 나오는 순간에 값을 업데이트 하고 가장 큰 값을 마지막에 반환해준다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize
        
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
        
        return profit