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

문제링크 : www.acmicpc.net/problem/11054

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

지난번 LIS로 백준의 전깃줄이라는 문제를 풀었다. 

LIS를 안다면 전깃줄 문제보다 쉽게 직관적으로 LIS로 풀면 된다는 것을 알 수 있다.

그래서 이 문제가 골드3인게 이해는 안가지만 어쨌든 풀이는 LIS로 해결했다.

정방향,역방향으로 증가하는 가장 긴 부분수열을 구해서 그 합이 최대인 값이 증가하다가 감소하는 가장 긴 부분수열의 길이일 것이다.

 

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

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int lis[][] = new int[N+2][2];
		int arr[] = new int[N+2];
		for(int i=1;i<=N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		lis[N+1][1] = 0;
		arr[N+1] = 0;
		for(int i=1;i<=N;i++) {
			for(int j=0;j<i;j++) {
				if(arr[i] > arr[j])
					lis[i][0] = Math.max(lis[j][0]+1,lis[i][0]);
			}
		}
		
		for(int i=N;i>=1;i--) {
			for(int j=N+1;j>i;j--) {
				if(arr[i] > arr[j]) {
					lis[i][1] = Math.max(lis[j][1]+1, lis[i][1]);
				}
			}
		}
		int ans = 0;
		for(int i=1;i<=N;i++) {
			ans = Math.max(ans, lis[i][0] + lis[i][1]);
		}
		System.out.println(ans-1);
	}

}