가장 긴 바이토닉 부분 수열

📍 문제 설명

💡 접근

가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열을 합친 문제이다.

2개로 나뉜 배열에 최대 수열 길이 각각 넣는다.

예를 들면 inc_dp[1] = {1,5} = 2 dec_dp[1] = {5,4,3,2,1} = 5 가 된다

이 두개를 합치면 {1,5 5,4,3,2,1}이 되고 중복되는 5를 제거 하여 {1,5,4,3,2,1}을 만든다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, answer;
    static int[][] board;
    static int[] arr, inc_dp, dec_dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = kb.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        inc_dp = new int[n];
        dec_dp = new int[n];

        /////////////////////////////////////////////
        for(int i = 0; i < n; i++) {
            inc_dp[i] = 1;
            //현재 항의 이전 항들을 탐색
            for(int j = 0; j < i; j++) {
                if(arr[j] < arr[i] && inc_dp[i] < inc_dp[j] + 1) {
                    inc_dp[i] = inc_dp[j] + 1;
                }
            }
        }
        /////////////////////////////////////////////

        for(int i = n-1; i >= 0; i--) {
            dec_dp[i] = 1;
            //현재 항의 이전 항들을 탐색
            for(int j = n-1; j > i; j--) {
                if(arr[j] < arr[i] && dec_dp[i] < dec_dp[j] + 1) {
                    dec_dp[i] = dec_dp[j] + 1;
                }
            }
        }

        int max = 0;
        for(int i = 0; i < n; i++) {
            if(max < inc_dp[i] + dec_dp[i]) max = inc_dp[i] + dec_dp[i];
        }
        System.out.println(max-1);
    }

    private void solution() {
    }

}