[백준] 가장 긴 바이토닉 부분 수열 (!) (11054번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 가장 긴 바이토닉 부분 수열 (11054번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

 

1. LIS를 구한다.

2. LDS를 구한다.

3. LIS + LDS - 1를 하여 가장 긴 바이토닉 부분 수열  DP를 구한다.

 

 

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

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

        // Right -> Left 인 오름차순
        for(int i=1; i<=N; i++){
            LIS_DP[i] = 1;

            // 0 ~ i 이전 원소 탐색
            for(int j=1; j<i; j++){

                // j 번째 원소가 i 번째 원소 보다 작음 AND i 번째 DP가 j 번째 DP + 1 값 보다 작음
                if (A[i] > A[j] && LIS_DP[i] < LIS_DP[j] + 1){
                    LIS_DP[i] = LIS_DP[j] + 1;
                }
            }
        }

        /*
        Left -> Right 인 오름차순 
        (= Right -> Left 인 내림차순)
        */
        for(int i=N; i>=1; i--){
            LDS_DP[i] = 1;

            for(int j=N; j>i; j--){
                if (A[i] > A[j] && LDS_DP[i] < LDS_DP[j] + 1){
                    LDS_DP[i] = LDS_DP[j] + 1;
                }
            }
        }

        // LIS 와 LDS의 중첩 배열
        int[] LBTS = new int[N+1]; // 가장 긴 바이토닉 부분 배열
        for(int i=1; i<=N; i++){
            LBTS[i] = LIS_DP[i] + LDS_DP[i] - 1;
        }

        // 가장 긴 바이토닉 부분 배열 길이 찾기
        int max = -1;
        for(int i=1; i<=N; i++){
            max = LBTS[i] > max ? LBTS[i] : max;
        }

        
        bw.write(max + "\n");
        bw.flush();
        bw.close();
    }
}