백준 11054 (가장 긴 바이토닉 부분 수열) - java

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

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

유형 : DP

접근 :

• i번째 수를 기준으로 봤을 때 1 -> i-1 까지의 수 중 i번째 수보다 작은 수들의 dp값 + 1 저장
• i번째 수를 기준으로 봤을 때 i+1 -> n까지의 수중 i번째 수보다 작은 수들의 dp값 + 1 저장

즉 가장 증가하는 부분 수열 (LIS)를 왼쪽과 오른쪽을 기준으로 2번 구해서 값을 구하면 된다.

 

전체 코드

import java.util.*;
import java.io.*;

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());
        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());
        }

        int[] left = new int[n+1];
        for(int i=1;i<=n;i++){

            int max = 0;
            for(int j=i-1;j>=1;j--){

                if(arr[i] > arr[j])
                    max = Math.max(left[j] + 1 , max);
            }

            left[i] = max;
        }

        int[] right = new int[n+1];
        for(int i=n;i>=1;i--){

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

            right[i] = max;
        }

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

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