BOJ 15487 A[j]-A[i]+A[l]-A[k]

BOJ 15487 A[j]-A[i]+A[l]-A[k]

[분류 : 다이나믹 프로그래밍]

 

[풀이]

  A[j] - A[i]를 먼저 계산해보자. 고정된 j에 대해 A[j]-A[i]가 최대가 되기 위해선 A[i]가 최소이어야 한다. 따라서 j를 순회하면서 [0, j) 구간에서 최소값을 유지하자.

  나머지 A[l] - A[k]을 구간 (j, N)에서 구하면 된다. 이 부분은 거꾸로 진행하면 된다. 즉 k를 N-2부터 시작해서 2까지 감소시켜나가면서 A[l]을 최대값으로 유지하며 진행하면 된다.

  이렇게 양쪽으로 최소/최대를 유지해나가며 그 중 최대값을 가져오면 AC를 받을 수 있다.

 

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6;
int main() {
    int N, A[MAX_N], i, ldp[MAX_N], rdp, mini = 1e9, maxi = -1e9, ans = -1e9;
    scanf("%d", &N);
    ldp[0] = rdp = -1e9;
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        if (i)
            ldp[i] = max(ldp[i - 1], A[i] - mini);
        mini = min(mini, A[i]);
    }
    maxi = A[N - 1];
    for (i = N - 2; i > 1; i--) {
        rdp = max(rdp, maxi - A[i]);
        ans = max(ans, rdp + ldp[i - 1]);
        maxi = max(maxi, A[i]);
    }
    printf("%d", ans);
    return 0;
}