[백준/c++] BOJ 25214 - 크림 파스타

https://www.acmicpc.net/problem/25214

25214번: 크림 파스타

 

문제 설명

빈 배열 A 뒤에 정수를 N번 추가하려고 한다.

수를 추가할 때마다 1 <= i <= j <= |A| 를 만족하는 정수 i, j에 대하여 Aj - Ai의 최댓값을 구한다.

|A|는 배열 A의 현재 길이, Ai는 i번째로 추가한 정수를 뜻한다.

N (1 <= N <= 200,000), Ai ( 1 <= Ai <= 1000000000)

해결

처음엔 문제를 잘못 이해하고 인덱스 상관없이 현재 배열에서의 최댓값과 최솟값을 빼 주었다.

하지만 Aj - Ai 연산에서 i와 j의 인덱스를 바꿀 수 없다.

간단하게 말하면 현재 배열에서 { 나중에 들어오는 수 - 이전에 들어온 수 } 의 최댓값을 구해야 한다.

 

따라서 배열에서 가장 작은 값을 저장하는 변수 MIN을 계속해서 갱신하면서, ans엔 { 현재 들어온 값 - 가장 작은 값} 과 이전 ans를 비교하여 더 큰 것이 저장되도록 구현하였다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	cin >> m;
	int MIN = m, ans = 0; n--; cout << ans << " ";

	while (n--) {
		cin >> m;

		if (m < MIN) MIN = m;

		ans = max(ans, m - MIN);
		cout << ans << " ";
	}
}