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

다이나믹 프로그래밍 문제입니다.

바이토닉 수열은 증가하는 수열과 감소하는 수열을 합쳐놓은 형태입니다.
처음 증가하는 수열을 찾고 증가가 끝난 시점의 위치에서 감소하는 수열을 이어붙이면 됩니다.

https://j3sung.tistory.com/941

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

위의 방식을 그대로 사용했습니다.
DP배열을 두개 만들어서 하나는 증가하는 부분수열로 만들고 하나는 감소하는 부분수열로 만들었습니다.

두 배열의 합이 가장 큰 인덱스가 가장 긴 바이토닉 부분수열입니다.
증가하는 부분수열 + 감소하는 부분수열이 가장 큰 값이므로 이 값을 결과값으로 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;
		
		int ans = 0;
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
		int[] upDP = new int[n+1];
		int[] downDP = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0; i<=n; ++i) {
			for(int j=i+1; j<=n; ++j) {
				if(arr[i] < arr[j]) {  
					upDP[j] = Math.max(upDP[j], upDP[i] + 1);
				}
				if(arr[n-i] < arr[n-j]) {  
					downDP[n-j] = Math.max(downDP[n-j], downDP[n-i] + 1);
				}
			}
		}
		
		for(int i=1; i<=n; ++i) {
			ans = Math.max(ans, upDP[i] + downDP[i]);
		}		
		
		bw.write(ans + "\n");		
		bw.close();
	}
}