[그리디] Greedy Algorithm / 자동차 단일 거래 이익 최대화하기 2

[문제그림]

문제링크

https://www.codetree.ai/missions/8/problems/max-profit-of-single-car-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 정렬은 불가능하다. 왜냐하면 파는 시점과 사는 시점이 섞일 수는 없기 때문이다. 
• 자동차를 파는 시점 기준(r)으로 그 전(0 ~ r - 1)에 언제 자동차를 사야했는가? 
  • 이익을 최대화하기 위해서는 사는 가격을 최소화해야한다.
  • 즉, 파는 시점 기준 첫 날부터 팔기 전 날까지의 가격 중 최솟값을 골라야한다.
• 그렇다면 팔기 전까지의 최소값을 기록해야한다. 
  • n이 100,000이므로 이중 for문은 당연히 사용할 수 없으니 다른 방법을 찾아야하는데...
  • 최소값을 누적하는 배열을 만들자!!
• 누적합과 비슷하게 진행한다.
  • 그 전과 비교하면서 최솟값 유지( pmin[i + 1] , pmin[i] )

inf = int(1e9)
pmin = [inf for _ in range(n + 1)]

ans = inf
for i in range(n):
    pmin[i + 1] = min(pmin[i], nums[i])

2. 코드(Python)

# 정렬은 불가
# 쌍 문제는 하나을 고정한다!!
n = int(input())
nums = list(map(int, input().split()))
# 누적 최소값
inf = int(1e9)
pmin = [inf for _ in range(n + 1)]

ans = inf
for i in range(n):
    pmin[i + 1] = min(pmin[i], nums[i])

ans = 0
for i in range(n):
    ans = max(ans, nums[i] -pmin[i + 1])

print(ans)