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

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

Best Time to Buy and Sell Stock - LeetCode

생각

수익을 최대화하기위한 서로 다른 두 날짜를 골라야하는 문제입니다.

문제 유형은 DP로 되어있지만, 슬라이딩 윈도우로 풀었습니다.

 

수익이 최대가 될려면 낮은가격에 사서 비싼가격에 팔아야 하므로, 투 포인터를 사용하여 왼쪽 포인터는 가격이 낮은 날짜가 되도록, 오른쪽 포인터는 가격이 높은 날짜가 되도록 조절해줍니다.

 

처음엔 주식을 살때 가격 >= 주식을 팔때 가격일때 단순히 왼쪽 포인터를 buy 1씩 증가시켜줬는데, 이렇게 하면 왼쪽포인터가 가리키고 있는게 낮은 가격임을 보장할 수 없습니다. 따라서 왼쪽 포인터를 오른쪽 포인터 값으로 갱신시켜줘야 합니다!

 

Python Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = 0
        sell = 1
        res = 0
        
        while True:
            if sell == len(prices) :
                break
            if prices[buy] < prices[sell]:
                profit = prices[sell]-prices[buy]
                if res <= profit:
                    res = profit
            else:
                buy = sell
            sell += 1
            
        return res