[BOJ] 8711 Odchudzanie

문제 링크

www.acmicpc.net/problem/8711

풀이

naive하게는 $i$번째 인덱스에서 그 뒤에 있는 모든 인덱스 $j$에 대해서 $w_i - w_j$의 최댓값을 구하는 방법이 있다.
이 경우 시간복잡도는 $O(n^2)$이며, 시간 내에 풀 수 없다.

이 문제는 다음과 같은 아이디어로 풀 수 있다.
앞에서부터 쭉 훑다가 지금까지 나온 값 중 가장 큰 값이 나온 상황을 가정하자.
그러면 지금까지 나온 값은 무시하고 최댓값을 선택하는 게 이득이다.
$i < j$이고 $w_i - w_j$에서 $w_i$가 크면 클 수록 최적이기 때문이다.

새로운 최댓값이 나왔다면 그 이후부터 등장하는 최솟값을 찾아야 한다.
그 이전에 등장한 최솟값은 쓸모가 없어지기 때문이다.

이런 방식으로 풀면 시간복잡도는 $O(n)$이 된다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int main() {
    fastio;
    int n;
    cin >> n;

    int ans = 0, mx = 0, mn = 1e9;
    for (int val, i = 0; i < n; ++i) {
        cin >> val;
        if (mx < val) mx = mn = val;
        else mn = min(mn, val);
        ans = max(ans, mx - mn);
    }

    cout << ans;

    return 0;
}