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

1. 문제

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

Best Time to Buy and Sell Stock - LeetCode

2. 접근 방법

앞에서부터 최저점을 계속 갱신해나가면서, 현재 값과 최저점을 뺐을 때 차이가 가장 컸을 때의 값을 반환한다.

 

나는 처음에 max값도 min값처럼 계속해서 갱신해나가려고 했는데, 

그렇게 되면 max값이 최저점을 만나기 전에 존재했던 max 값인 경우에도 들어가게 된다.

 

그래서 min값은 계속 갱신하고, 그에따른 profit만 계속해서 갱신해나가는 걸루 만들었다

3. 코드

python

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

4. 마치며

마치며~!