[백준 / Python 파이썬] 25214번 - 크림 파스타

[Silver IV] 크림 파스타 - 25214

---

문제 링크

분류

다이나믹 프로그래밍, 그리디 알고리즘

문제 설명

민겸이는 크림 파스타를 먹다가 다음과 같은 문제를 생각해냈다.

빈 배열 A\(A\)가 있다. 민겸이는 A\(A\)의 맨 뒤에 정수를 N\(N\)번 추가하려고 한다. 수를 그냥 추가하기만 하면 재미없으니, 수를 추가할 때마다 1 ≤ i\(i\) ≤ j\(j\) ≤ |A|\(|A|\) 를 만족하는 정수 i\(i\), j\(j\)에 대하여 Aj−Ai\(A_j - A_i\)의 최댓값을 구하려고 한다. |A|\(|A|\)는 배열 A\(A\)의 현재 길이를 뜻하고, Ai\(A_i\)는 민겸이가 i\(i\)번째로 추가한 정수를 뜻한다.

민겸이가 식사를 마치기 전에 이 문제를 대신 풀어보자.

입력

입력은 두 줄로 주어진다.

첫 번째 줄에는 민겸이가 배열에 추가하려는 정수의 개수 N\(N\)이 주어진다.

두 번째 줄에는 A1\(A_1\)부터 AN\(A_N\)까지 N\(N\)개의 정수가 공백으로 구분되어 주어진다.

출력

각 Ai\(A_i\)가 추가된 직후의 문제의 답 N\(N\)개를 공백으로 구분하여 출력한다.

---

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

DP = [0] * N
min_num = A[0]
for i in range(1, N):
    min_num = min(min_num, A[i])
    DP[i] = max(DP[i - 1], A[i] - min_num)

print(*DP)