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

문제링크 : https://www.acmicpc.net/problem/11054

 

 

문제 분석

 

먼저 부분 수열이라는 것에 대해 다시 한번 집고 넘어가보면 

원래 수열에서 일부 원소를 순서를 유지하면서 제거하여 만든 수 ➔ 연속되지 않아도 됨.

 

 

사고 순서

 

기존에 풀어보았던 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열에서 영감을 얻음

➔ 아 이 문제는 두 가지를 다 구해서 합의 최대값을 구해야겠다.

 

for (int i = 1; i <= N; i++) {
    for (int j = 1; j < i; j++) {
        if (arr[i] > arr[j]) {
            dp_ASC[i] = Math.max(dp_ASC[i], dp_ASC[j] + 1);
        }
    }
}

 

증가 부분 수열은 앞에서부터 구한다.

 

for (int i = N; i >= 1; i--) {
    for (int j = N; j > i; j--) {
        if (arr[i] > arr[j]) { // 감소하는 부분 수열
            dp_DESC[i] = Math.max(dp_DESC[i], dp_DESC[j] + 1);
        }
    }
}

 

감소하는 부분은 뒤에서부터 구한다.

 

 

int max_length = 0;
for (int i = 1; i <= N; i++) {
    max_length = Math.max(max_length, dp_ASC[i] + dp_DESC[i] - 1);
}

 

최대 길이를 구한다 이때 -1 (중복 카운트 제외) 을 빼는 것을 까먹으면 안된다.

 

 

 

전체 코드

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 수열의 크기
        int []arr = new int[N+1];
        int []dp_ASC = new int[N+1]; // 증가하는 수열
        int []dp_DESC = new int[N+1]; // 감소하는 수열

        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
            dp_ASC[i] = 1;
            dp_DESC[i] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp_ASC[i] = Math.max(dp_ASC[i], dp_ASC[j] + 1);
                }
            }
        }

        for (int i = N; i >= 1; i--) {
            for (int j = N; j > i; j--) {
                if (arr[i] > arr[j]) {
                    dp_DESC[i] = Math.max(dp_DESC[i], dp_DESC[j] + 1);
                }
            }
        }

        int max_length = 0;
        for (int i = 1; i <= N; i++) {
            max_length = Math.max(max_length, dp_ASC[i] + dp_DESC[i] - 1);
        }

        System.out.println(max_length);
    }
}