[코드트리 파이썬] 자동차 단일 거래 이익 최대화하기 2

문제

---

풀이

그리디로 해결해야 하는 문제이다.

완전탐색으로 해결하려 하면 시간초과가 나오기 때문이다.

 

따라서 가장 최선의 경우의 수를 뽑아야한다.

가장 좋은 방법은 파는 시점을 기준으로 하는것이다.

 

배열을 한번 순회하며 최소값을 갱신하며 파는 시점을 기준으로 최소값을 빼주면 

O(n)의 시간으로 해결할 수 있다.

 

for i in range(n):
    profit = cost[i] - minCost

    if profit > maxProfit:
        maxProfit = profit
    
    if minCost > cost[i]:
        minCost = cost[i]

 

위의 코드로 해결할 수 있다.

현재 가격과 최소값을 빼준 후 

최대값보다 계산값이 크면 최대값을 갱신해준다.

또한 현재값이 최소값보다 작을경우 최소값을 갱신해준다.

 

 

 

코드

n = int(input())
cost = list(map(int, input().split()))

maxProfit = 0
minCost = cost[0]

for i in range(n):
    profit = cost[i] - minCost

    if profit > maxProfit:
        maxProfit = profit
    
    if minCost > cost[i]:
        minCost = cost[i]

print(maxProfit)