[백준 25214번] 크림 파스타 (C++)

문제링크 : https://www.acmicpc.net/problem/25214

25214번: 크림 파스타

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, num, minV;
int arr[200001], dp[200001];

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

    cin >> N;
    for(int i=0; i<N; i++) cin >> arr[i];

    minV = arr[0]; //초기값

    for(int i=1; i<N; i++)
    {
        dp[i] = max(dp[i-1], arr[i]-minV); //Aj-Ai 최대값
        minV = min(minV, arr[i]); //Ai 최솟값
    }

    for(int i=0; i<N; i++) cout << dp[i] << " ";

    return 0;
}

 

Ai에 대한 최소값을 담기 위해 따로 변수 minV를 선언하고 초기값으로 arr[0]을 넣어준다.

 

이후 반복문을 i=1부터 ~ N-1까지 돌며 기존 값이 더 큰지 현재 Aj-Ai 값이 더 큰지를 판별한다.

판별을 한 이후에 Ai의 최소값을 갱신해주어 다음 탐색때 Aj-Ai의 최대값을 찾을 수 있도록 한다.