[BOJ 11054] 가장 긴 바이토닉 부분 수열 (Java)

문제

https://www.acmicpc.net/problem/11054

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

 

풀이

기준 숫자에서 왼쪽과 오른쪽을 나눈다. 

left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수

right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수

left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문)

 

차례대로 index를 증가 또는 감소 시키면서 채워나간다. 

 

예)

10

1 5 2 1 4 3 4 5 2 1

idx	1	2	3	4	5	6	7	8	9	10
num	1	5	2	1	4	3	4	5	2	1
left	0	1	1	0	2	2	3	4	1	0
right	0	0	1	0	3	2	2	2	1	0

8번째 Index가 기준 숫자가 되는 것이 가장 긴 바이토닉 수열을 만들 수 있다. 

 

소스코드

package dp;

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

public class BOJ11054 {

    public static int N;
    public static void pro() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[N+1];
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // i번째 수 기준으로 왼쪽을 살펴보면서 오름차순 수의 최대 개수를 count
        int[] left = new int[N+1];
        for(int i = 1; i <= N; i++){
            if(i == 1) {
                left[i] = 0;
                continue;
            }
            int max = 0;
            boolean exist = false;
            for(int j = 1; j < i; j++){
               if(arr[i] > arr[j]){
                   max = Math.max(max, left[j]);
                   exist = true;
               }
            }

            left[i] = exist ? max + 1 : 0;
        }

        // 오른쪽도 반대로
        int[] right = new int[N+1];
        for(int i = N; i >= 1; i--){
            if(i == N) {
                right[i] = 0;
                continue;
            }
            int max = 0;
            boolean exist = false;
            for(int j = N; j > i; j--){
                if(arr[i] > arr[j]){
                    exist = true;
                    max = Math.max(max, right[j]);
                }
            }
            right[i] = exist ? max + 1 : 0;
        }

        int max = 0;
        for(int i = 1; i <= N; i++){
            max = Math.max(max, right[i]+left[i]);
        }

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

    public static void main(String[] args) throws Exception {
        pro();
    }
}