배열에 수가 추가될때마다 원소간 차이의 최댓값 구하기

1. 문제

 

25214번: 크림 파스타 (acmicpc.net)

25214번: 크림 파스타

 

2. 풀이

 

그냥 단순하게 생각해서 배열 원소의 최댓값과 최솟값을 기억해두고,

 

n개의 원소를 처음부터 순회해서, A[i]가 최대인지 검사하고 최대라면 최댓값을 갱신한다음에,

 

dp[i]에 최댓값 - 최솟값을 넣어주면 되는거 아녀?

 

새로 들어온 값이 최댓값이 아니라면, dp[i]는 이전에 구한 dp[i-1]과 같을거고

 

최댓값이 아닌 경우에 당연히 A[i]가 최솟값이 될 자격이 있으니까 A[i]가 최솟값인지 검사하고

 

A[i]가 최솟값이라면 최솟값을 갱신해준다

 

여기서 $i \leq j$인 i,j에 대하여 A[j] - A[i]의 값을 구하는거니까 A[i]가 최솟값으로 갱신된다면, 최댓값도 A[i]로 갱신시켜야한다

 

from sys import stdin

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

dp = [0]*n

max_A = A[0]
min_A = A[0]

for i in range(1,n):
    
    if max_A < A[i]:
        
        max_A = A[i]
        
        dp[i] = max_A - min_A
    
    else:
        
        dp[i] = dp[i-1]

        if min_A > A[i]:
            
            min_A = A[i]
            max_A = A[i]
    

print(*dp)

 

근데 이러면 오답이야

 

A = 3 4 7 1 2라고 한다면...

 

0 1 4 4 4가 나와야 하는데

 

0 1 4 4 1이 나오니까..

 

제약조건 $i \leq j$에 대해 A[j] - A[i]의 최댓값을 구하다보니, 반드시 배열의 최댓값 - 최솟값이 A[j] - A[i]의 최대라는 보장은 없다

 

사고방식을 바꿔서

 

dp[i]가 i번째 수가 들어올때 A[j] - A[i]의 최대라고 정의한다면..

 

i번째 수가 들어올때마다 만들 수 있는 A[j] - A[i]의 최댓값은 x = A[i] - min_A으로 주어진다.

 

그러므로 이전 i - 1번째 구해놓은 최댓값 dp[i-1]과 비교해서 x가 더 크다면...

 

dp[i] = x로 정의한다.

 

x가 dp[i-1]보다 더 작다면, dp[i] = dp[i-1]이고, min_A가 갱신될 수 있는지 체크한다

 

min_A가 A[i]보다 크다면, A[i]를 min_A로 갱신한다

 

from sys import stdin

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

dp = [0]*n

min_A = A[0]

for i in range(1,n):
    
    x = A[i] - min_A

    if x > dp[i-1]:
        
        dp[i] = x
    
    else:
        
        dp[i] = dp[i-1]

        if min_A > A[i]:
            
            min_A = A[i]
    
print(*dp)