[LEETCODE] 121: Best Time to Buy and Sell Stock(Python)

Best Time to Buy and Sell Stock - LeetCode

문제 설명

날짜별 주식의 가격이 주어질 때, 최대 이익(판 가격-산 가격)을 구해보자. 적자일 때는 이익을 0으로 출력한다!

나의 풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy=0
        answer=0
        for i in range(1,len(prices)):
            sell=i
            profit=prices[sell]-prices[buy]
            if prices[buy]<prices[sell]:
                answer=max(profit,answer)
            else:
                buy=sell # sell == i
        
        return answer

따로 dp테이블을 만들지 않고 풀었다. for문으로 파는 날짜를 돌리고, 이익이 있는 경우(0보다 큰 경우)에만 최대 이익을 업데이트한다. 이익이 없는 날에는 사는 날짜를 현재 날짜로 업데이트한다.

시간복잡도

for문에서 O(n)의 시간복잡도를 가진다.