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

https://www.acmicpc.net/problem/11054

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

바이토닉 수열이란 특정값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순인 수열을 말한다.

 

LIS(최장 증가 부분 수열) 문제와 비슷하다.

왼쪽과 오른쪽으로 각각 탐색하여 더하고 중복을 빼면 된다.

 

 

다음은 예제 입력인 {1 5 2 1 4 3 4 5 2 1} 수열에서 왼쪽, 오른쪽 각각 LIS를 탐색한 결과이다.

 

두 수열을 합친 결과이다.

수열을 합친 후 자기 자신이 중복되어 있으므로 -1을 해주어 결과를 구한다.

따라서 답은 최댓값인 8에서 -1을 한 7이다.

 

import java.util.*;

public class Main {
	static int n;
	
	static int dpl[],dpr[], result[],arr[];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dpl = new int[n+1];
        dpr = new int[n+1];
		arr = new int[n+1];
		
		for(int i=1;i<=n;i++) {
			arr[i] = sc.nextInt();
		}
	
		dpl[1] =1; // 왼쪽부터 시작하는 LIS
		dpr[n] = 1; // 오른쪽부터 시작하는 LIS
        
        for(int i=2;i<=n;i++) { // 왼쪽에서 시작하는 LIS
			dpl[i] =1;
			for(int j=1;j<i;j++) {
				if(arr[i]>arr[j]) {
					dpl[i] = Math.max(dpl[i], dpl[j]+1);
				}
			}
		}
        
		for(int i=n-1;i>0;i--) { // 오른쪽에서 시작하는 LIS
			dpr[i] =1;
			for(int j=n;j>i;j--) {
				if(arr[i]>arr[j]) {
					dpr[i] = Math.max(dpr[i], dpr[j]+1);
				}
			}
		}
		
		
		int ret[]=new int[n+1];
		for(int i=1;i<=n;i++) { // 두 배열의 값들을 더해준다.
			ret[i] = dpr[i] + dpl[i];
			
		}
		
        int max=0;
		for(int i=1;i<=n;i++) {
			if(ret[i] > max) {
				max =ret[i] ;
			}
		}
		
		System.out.println(max-1); // 최댓값을 찾아 -1
	
	}
	
}