최대값 찾기 알고리즘 (Finding Maximum)

최대값 찾는 방법은 1. 정렬을 하거나 2. 하나하나 값을 비교해서 하면 되지만, 이번 알고리즘에는 제한이 있다.

 

알고리즘의 시간복잡도를 O(n)이 되도록 해야한다.

 

시간복잡도가 O(n)이 되기 위해선, 반복문이 이중으로 존재하면 안된다. 그러므로 다음과 같이 작성한다.

price_tag = [10300,9600,9800,8200,7800,8300,9500,9800,10200,9500]

def max_profit(prices):
    n = len(prices)
    maxprofit = 0
    minprice = prices[0]
    
    for x in range(1,n):
        profit = prices[x] - minprice
        
        if profit > maxprofit:
            maxprofit = profit
        if prices[x] < minprice:
            minprice = prices[x]
            
    return maxprofit

print(max_profit(price_tag))