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

문제 풀이

주식의 값들이 주어질 때, 어떤 날에 사거나 팔아서 가장 수익을 많이 낼 수 있는 값을 찾는 문제이다.
나는 dp로 이 문제를 풀었다.

1. dp 리스트를 만들어준다.

2. 산 주식을 첫 번째 리스트 원소로 지정해준다.

3. for문을 두 번째 원소부터 시작하여 탐색한다.

4. dp 리스트에 현재 주식 값에서 산 주식을 빼준 값을 넣어준다.

5. 현재 주식이 산 주식보다 싸다면 현재 주식을 산 주식으로 바꿔준다.

6. dp 리스트에서 가장 큰 값을 return 해준다.

답

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0] * len(prices) ## 1. dp 리스트를 만들어준다.
        buy = prices[0] ## 2. 산 주식을 첫 번째 리스트 원소로 지정해준다.
        for i in range(1, len(prices)): ## 3. for문을 두 번째 원소부터 시작하여 탐색한다.
            dp[i] = prices[i] - buy ## 4. dp 리스트에 현재 주식 값에서 산 주식을 빼준 값을 넣어준다.
            buy = min(buy, prices[i]) ## 5. 현재 주식이 산 주식보다 싸다면 현재 주식을 산 주식으로 바꿔준다.
        return max(dp) ## 6. dp 리스트에서 가장 큰 값을 return 해준다.