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

문제

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

아이디어

• dp[n]을 n번째 자리에서 가장 긴 바이토닉 부분수열의 길이라고 가정한다.
• 정방향과 역방향을 각각 구한다.
• n번째 자리의 합 중 최댓값 - 1 이 정답이다.
• -1 은 교집합 부분을 제외한 것이다.

예상 시간 복잡도

• 이중 for문으로 정방향과 역방향 DP 배열 구함
• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_11054 {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n]; //수열
        int[] dp = new int[n];  //정방향 바이토닉 수열
        int[] dp_r = new int[n];//역방향 바이토닉 수열

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
            dp_r[i] = 1;
        }

        //정방향
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (arr[i] > arr[j] && dp[i] + 1 == dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        //역방향
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                if (arr[i] > arr[j] && dp_r[i] + 1 == dp_r[j] + 1) {
                    dp_r[i] = dp_r[j] + 1;
                }
            }
        }

        int max = 0;

        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[i] + dp_r[i]);
        }

        System.out.println(max - 1);
    }
}