[BOJ 11054] 가장 긴 바이토닉 부분 수열 (Java)

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

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

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

public class Main_BOJ_11054 {
	static int N;
	static int[] arr;
	static int[] dp_up;
	static int[] dp_down;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		arr=new int[N];
		dp_up=new int[N];
		dp_down=new int[N];
		StringTokenizer st=new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		for (int i=0; i<N; i++) {
			dp_up[i]=1;
			for (int j=0; j<i; j++) {
				if (arr[j]<arr[i] && dp_up[j]+1>dp_up[i]) {
					dp_up[i]=dp_up[j]+1;
				}
			}
		}
		for (int i=N-1; i>=0; i--) {
			dp_down[i]=1;
			for (int j=i+1; j<N; j++) {
				if (arr[i]>arr[j] && dp_down[j]+1>dp_down[i]) {
					dp_down[i]=dp_down[j]+1;
				}
			}
		}
		int max=-1;
		for (int i=0; i<N; i++) {
			int sum=dp_up[i]+dp_down[i];
			if (sum>max) {
				max=sum;
			}
		}
		System.out.println(max-1);
	}

}

dp 배열을 두 쌍 만들어서 하나는 앞에서부터 증가하는 수열을 찾는 배열, 다른 하나는 뒤에서부터 시작해서 증가하는 수열을 찾는 배열로 한다.

 

바이토닉 부분 수열이 최장이 되는것은 이 dp 배열 2개를 합한 값이 최대가 되는 것이다.

마지막에는 1을 빼줘서 2번 수가 더해지는 것을 막아주자.