[BOJ] 11054. 가장 긴 바이토닉 부분 수열

문제 원본 : https://www.acmicpc.net/problem/11054

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] arr = new int[n];
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];

        for (int i = 0; i < n; ++i) {
            arr[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; ++i) {
            dp1[i] = 1;
            dp2[n - i - 1] = 1;
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                }

                if (arr[n - i - 1] > arr[n - j - 1]) {
                    dp2[n - i - 1] = Math.max(dp2[n - i - 1], dp2[n - j - 1] + 1);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, dp1[i] + dp2[i]);
        }

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

• 풀이법이 생각나지 않아 다른 블로그를 참고하였다.
• 가장 긴 증가하는 부분 수열을 앞에서 한 번, 뒤에서 한 번 적용하면 된다.
• 각각 구한 배열의 값을 인덱스 별로 더해줘서 나온 가장 큰 값이 답이 된다.
• 자기 자신은 중복되기 때문에 1을 빼줘야 한다.