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

문제 링크

www.acmicpc.net/problem/15487

풀이 1

dp 테이블을 다음과 같이 정의한다.
dp[n]: [0, n] 구간에서 두 인덱스 i, j (i < j)를 선택했을 때 A[j] - A[i]의 최댓값

prefix는 이렇게 완성하고, suffix dp는 만들어도 상관없지만 뒤에서부터 순회하면서 온라인으로 처리할 수 있다.
그렇게 두 구간의 최댓값을 더하면 답이 된다.

이 풀이는 시간복잡도와 공간복잡도 둘다 $O(N)$이다.

C++ 코드

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)size(x)
#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 arr[1000000];
    for (int i = 0; i < N; ++i) cin >> arr[i];

    int prefixDP[1000000];
    for (int mx = arr[1], mn = arr[0], opt = -2000000, i = 1; i < N - 2; ++i) {
        mx = max(mx, arr[i]);
        if (mn > arr[i - 1]) {
            mn = arr[i - 1];
            mx = arr[i];
        }
        opt = max(opt, mx - mn);
        prefixDP[i] = opt;
    }

    int ans = -4000000;
    for (int mx = arr[N - 1], mn = arr[N - 2], opt = -2000000, i = N - 2; i > 1; --i) {
        mn = min(mn, arr[i]);
        if (mx < arr[i + 1]) {
            mx = arr[i + 1];
            mn = arr[i];
        }
        opt = max(opt, mx - mn);
        ans = max(ans, opt + prefixDP[i - 1]);
    }

    cout << ans;

    return 0;
}

풀이 2

dp 테이블을 다음과 같이 정의한다.
dp[n][i]: [0, n] 구간에서 i번째 인덱스를 선택했을 때 최댓값

• dp[0]의 경우
  • dp[0][0]은 -A[0]의 값과 같다.
  • dp[0][1~3]은 존재하지 않는다.
• dp[1]의 경우
  • dp[1][0]은 max(-A[0], -A[1])의 값과 같다.
  • dp[1][1]은 dp[0][0]+A[1]의 값과 같다.
  • dp[1][2~3]은 존재하지 않는다.
• dp[2]의 경우
  • dp[2][0]은 max(-A[0], -A[1], -A[2])의 값과 같다.
  • dp[2][1]은 max(dp[0][0]+A[1], dp[1][0]+A[2])의 값과 같다.
  • dp[2][2]은 dp[1][1]-A[2]의 값과 같다.
  • dp[2][3]은 존재하지 않는다.
• dp[3]의 경우
  • dp[3][0]은 $\max_{0 \leq i \leq 3} A[i]$의 값과 같다.
  • dp[3][1]은 $\max_{0 \leq i \leq 2} dp[i][0]+A[i+1]$의 값과 같다.
  • dp[3][2]은 max(dp[1][1]-A[2], dp[2][1]-A[3])의 값과 같다.
  • dp[3][3]은 dp[2][2]+A[3]의 값과 같다.

이런 식으로 진행하면, 슬라이딩 윈도우를 통해 dp[4] 배열로 관리가 가능함을 알 수 있다.

이 풀이는 시간복잡도는 $O(N)$으로 동일하며 공간복잡도는 $O(1)$이다.

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());

        StringTokenizer st = new StringTokenizer(in.readLine());
        int[] dp = new int[4];
        for (int i = 0; i < 4; ++i) dp[i] = -2_000_000;

        for (int val, i = 0; i < N; ++i) {
            val = Integer.parseInt(st.nextToken());
            dp[3] = Math.max(dp[3], dp[2] + val);
            dp[2] = Math.max(dp[2], dp[1] - val);
            dp[1] = Math.max(dp[1], dp[0] + val);
            dp[0] = Math.max(dp[0], -val);
        }

        System.out.println(dp[3]);
    }
}