문제

• 가격 리스트 prices
• prices[i]는 ith 날의 가격
• 하루에 사고, 그 이후에 판매하여 최대 수익을 얻고 싶다
• profit 없으면 0 return

풀이

• i번째까지 갔을 때, 0 ~ i-1 중 가장 저렴하게 구매한 금액을 알고 있으면 됨
• 브루트포스면 O(n**2)
• 탐색 결과를 저장하는 리스트를 만들어서, dp처럼 dp[k]= min(dp[k-1], prices[k]) -> k번째까지 왔을 때, 최소로 구매한 비용 얼만지 알 수 있음. O(n)
• maxProfit 변수 두고 매 반복마다 비교 후, 값이 크면 갱신

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        minBuy = [0 for _ in range(length)]
        maxProfit = 0
        
        minBuy[0] = prices[0]
        
        for day, price in enumerate(prices):
            if day == 0:
                pass
            else:
                maxProfit = max(price - minBuy[day-1], maxProfit) # does today's selling make the best profit?
                minBuy[day] = min(minBuy[day-1], price) # Is today's price lowest buying price?
        return maxProfit

결과

easy라서 easy하구만~!

브루트포스

궁금해서 브루트 해봤는데

    def maxProfit(self, prices: List[int]) -> int:
        maxiProfit = 0
        for i, selling in enumerate(prices):
            for j, buying in enumerate(prices[:i]):
                maxiProfit = max(maxiProfit, selling - buying)
        return maxiProfit

시간초과 ㅋㅋㅋ