[백준 11054 JAVA] 가장 긴 바이토닉 부분수열

 

증가하는 가장 긴 수열 응용 문제

 

다른 문제들과 다르게 이 문제에서는 증가하다가 피크를 찍고 다시 감소하는 부분까지 수열이 이어진다.

 

내가 생각해 낸 방법은 앞에서부터 증가하는 수열, 뒤에서부터 증가하는 수열을 구해서 한 점에서 만나면 된다.

 

각각 구한후 두개를 더한 최대값을 찾으면 답이 구해진다.

 

 

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

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];
        int dp[] = new int[N];
        int dp2[] = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
            dp2[i] = 1;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                if (arr[N-i-1] > arr[N-j-1]) {
                    dp2[N-i-1] = Math.max(dp2[N-i-1], dp2[N-j-1] + 1);
                }
            }
        }
        
        int result = 0;
        for (int i = 0; i < N; i++) {
            result = Math.max(result, dp[i] + dp2[i]-1);
        }
        System.out.println(result);
    }
}