[알고리즘] 백준 - 11054 ( 가장 긴 바이토닉 부분 수열) / 자바

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

class Solution {
	static int N;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		int[] reverse = new int[N];
		int[] reverse_dp = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			reverse[N-i-1] = arr[i];
		}
		
		LIS(arr , dp);
		LIS(reverse,reverse_dp);
	
		
		
		int maxValue = 0;
		for (int i = 0; i < N; i++) {
			maxValue = maxValue > (dp[i]+reverse_dp[N-i-1]) ? maxValue : (dp[i]+reverse_dp[N-i-1]);
		}
		System.out.print(maxValue-1);
	}
	
	static void LIS(int[] arr , int[] dp) {
		int maxIndex;
		int maxValue;
		dp[0] = 1;
		for (int i = 1; i < N; i++) {
			if (arr[i] == arr[i - 1]) {
				dp[i] = dp[i - 1];
			} else {
				maxIndex = -1;
				maxValue = 1;
				for (int j = i - 1; j >= 0; j--) {
					//현재 값보다 작고 길이가 긴 인덱스를 찾음
					if (arr[j] < arr[i] && maxValue <= dp[j]) {
						maxValue = dp[j];
						maxIndex = j;
					}
				}
				// 자신보다 작은 값이 없으면 1을 , 있으면 가장 큰 길이를 가지는 값에 +1
				dp[i] = maxIndex == -1 ? 1 : dp[maxIndex] + 1;
			}
		}	
	}
}

가장 긴 증가하는 부분 수열을 순서대로 한번 , 역순으로 한번 구한 뒤 더해주면 쉽게 찾을 수 있다.