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

---

바이토닉 부분수열의 길이를 구하기 위해서는,

 

어떤 인덱스에 위치한 수를 기준으로 앞에서부터 시작하는 가장 긴 증가하는 부분수열의 길이와

 

뒤에서부터 시작하는 가장 긴 부분수열의 길이를 알아야겠다 생각이 들었다.

 

 

[JAVA] 백준 11053번 【가장 긴 증가하는 부분 수열】

 

원리는 위 문제와 동일하다.

 

대신 앞에서 부터 시작하는 증가 부분수열을 기록해놓을 dpAsc배열과 뒤에서 부터 시작하는 증가 부분수열을 기록해놓을 dpDsc 두개의 dp배열을 생성하였다.

 

그리고 dpAsc와 dpDsc의 같은 인덱스 값의 합에서 해당 인덱스값은 중복이 되기 때문에, 1을 뺀 값이 바이토닉 부분수열의 길이가 된다.

 

 

위 그림을 보면 이해하기 쉬울 것이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int[] dpAsc = new int[N + 1];
		int[] dpDsc = new int[N + 1];
		int[] dpTotal = new int[N + 1];
		int[] array = new int[N + 1];
		String[] input = br.readLine().split(" ");
		for (int i = 0; i < input.length; i++) {
			array[i + 1] = Integer.valueOf(input[i]);
			dpAsc[i+1]=1;
			dpDsc[i+1]=1;
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<i;j++) {
				if(array[i]>array[j] && dpAsc[i]<dpAsc[j]+1) {
					dpAsc[i]=dpAsc[j]+1;
				}
				if(array[N+1-i]>array[N+1-j] && dpDsc[N+1-i]<dpDsc[N+1-j]+1) {
					dpDsc[N+1-i]=dpDsc[N+1-j]+1;
				}
			}
		}
		for(int i=1;i<=N;i++) {
			dpTotal[i]=dpAsc[i]+dpDsc[i]-1;
		}
//		System.out.println(Arrays.toString(array));
//		System.out.println(Arrays.toString(dpAsc));
//		System.out.println(Arrays.toString(dpDsc));
//		System.out.println(Arrays.toString(dpTotal));
		Arrays.sort(dpTotal);
		System.out.println(dpTotal[N]);
		
	}
}