백준 11054번 - 가장 긴 바이토닉 부분 수열 (Java)

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

11054번: 가장 긴 바이토닉 부분 수열

코드 :

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

public class Main {
    static int dp[];
    static int dpRe[];
    static int seq[];

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

        dp = new int[N+1];
        dpRe = new int[N+1];
        seq = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        // LIS
        for (int i = 1; i <= N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (seq[j] < seq[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        // LIS 역순
        for (int i = N; i > 0; i--) {
            dpRe[i] = 1;
            for (int j = N; j > i; j--) {
                if (seq[j] < seq[i] && dpRe[j] + 1 > dpRe[i]) {
                    dpRe[i] = dpRe[j] + 1;
                }
            }
        }

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(dp[i] + dpRe[i], max);
        }

        // dp[i]는 해당 인덱스까지의 최장 증가 수열이다. 1부터 시작하는 두 수열을 합치므로 1을 빼줘야한다.
        System.out.println(max - 1); 
    }

}

풀이 :

LIS를 역순으로 한번 더 적용하고, 메모이제이션한 값을 더해서 -1 했다. 사실상 LIS, LDS 문제를 합쳐놓은 문제다.