BOJ) 가장 긴 바이토닉 부분 수열 (11054 번)

가장 긴 바이토닉 부분 수열

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

바이토닉 부분 수열은 요소들의 증감이 변곡점을 하나 이하로 가진 부분 수열이다.

즉, {1, 3, 5, 6, 4} 혹은 {1,2} 혹은 {7,3,5}와 같은 수열들이 바이토닉 수열이라 할 수 있다.

 

이 문제를 풀기 위해서는 LIS, LDS에 대한 개념이 있어야한다고 한다.

 

LIS => Longest Increasing Subsequence    (최장 증가 부분 수열)
LDS => Longest Decreasing Subsequence  (최장 감소 부분 수열)

 

LIS에는 0~n까지 진행하면서, 각 인덱스 전까지 연속으로 증가하고 있는 수의 개수를 저장한다.

LDS는 반대로 감소하고 있는 개수를 저장한다.

 

따라서, LIS의 값과 LDS의 값을 더하면 변곡점을 하나만 가진 바이토닉 부분 수열이 되는 것이다.

이 때, LIS와 LDS에 특정 인덱스에 대한 개수가 각각 +1 씩 되어있다. => +2

중복된 카운트를 지워주기 위해 -1을 취한 값의 최대 값이 가장 긴 바이토닉 부분 수열이 된다.

 

더 자세한 설명은 여기 블로그를 참고 (LIS와 LDS에 대한 설명이 잘 나와있다)

 

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] sequence = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            sequence[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        solution(n, sequence);
    }

    private static void solution(int n, int[] sequence) {
        int[] lis = getLIS(n,sequence);
        int[] lds = getLDS(n,sequence);

        int answer =0;
        for(int i=0; i<n; i++) {
            answer = Math.max(answer, lis[i]+lds[i]);
        }

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

    private static int[] getLIS(int n, int[] sequence) { // 최장 증가 부분 수열
        int[] lis = new int[n];
        for(int i=0; i<n; i++) {
            lis[i] = 1;
            for(int j=0; j<i; j++) {
                // j번째 원소가 i번째 원소보다 작고 dp[i]가 dp[j] +1 값보다 작은경우
                if(sequence[j] < sequence[i] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }
        return lis;
    }

    private static int[] getLDS(int n, int[] sequence) { // 최장 감소 부분 수열
        int[] lds = new int[n];
        for(int i=n-1; i>=0; i--) {
            lds[i] =1;
            for(int j=n-1; j>i; j--) {
                if(sequence[j] < sequence[i] && lds[i] < lds[j] +1) {
                    lds[i] = lds[j]+1;
                }
            }
        }
        return lds;
    }
}