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

문제 출처: www.acmicpc.net/problem/11054

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

: 주어진 수열에서 가장 긴 바이토닉 부분 수열의 길이를 구해야 한다.

: 바이토닉 수열은 어느 한 수를 기준으로 앞부분은 그 수까지 단순 증가 형태로 이루어지고, 해당 수 뒤 쪽은 단순 감소하는 형태를 나타내는 수열이다.

: 수열의 수를 순회하며 기준이 되는 수로 만들고, 그 기준으로 앞쪽과 뒤쪽을 가장 긴 증가 부분 수열과 가장 긴 감소 부분 수열의 길이를 각각 구해 더해준 값 중 최대값을 구한다.

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

public class 가장긴바이토닉부분수열 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		
		int[] list = new int[N];
		st = new StringTokenizer(br.readLine());
//		int maxIdx = 0;
//		int max = 0;
		for(int i = 0; i < N; i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		int ans = 0;
		for(int k = 0; k < N; k++) {
			int[] LIS = new int[N];
			int[] LIS2 = new int[N];
			int size = 0;
			int size2 = N-1;
			for(int i = 0; i < N; i++) {
				if(i <= k) {
					int idx = Arrays.binarySearch(LIS, 0, size,list[i]);
					if(idx < 0) idx = Math.abs(idx)-1;	
					LIS[idx] = list[i];
					if(idx == size) size++;
				}else {
					if(list[i] == LIS[size-1]) continue;
					int idx = Arrays.binarySearch(LIS2, size2, N,list[i]);
					if(idx < 0) idx = Math.abs(idx)-2;	
					LIS2[idx] = list[i];
					if(idx == size2) size2--;
				}
			}
//			System.out.println("k = " + k);
//			System.out.println(Arrays.toString(LIS));
//			System.out.println(Arrays.toString(LIS2));
			int res = size+N-size2-1;
			ans = ans > res ? ans : res;
		}
		System.out.println(ans);
		
	}
}