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

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

---

풀이

가장 긴 바이토닉 부분 수열은 앞에서부터 가장 긴 증가하는 부분 수열의 개수 + 뒤에서부터 가장 긴 증가하는 부분 수열의 개수에다가 자기 자신은 두 번 들어갔으므로 1을 빼어 해결할 수 있었습니다.

 

예를 들어, 수열 1 5 2 1 4 3 4 5 2 1의 경우를 보면,

빨간색으로 쓴 1번은 앞에서부터 증가하는 부분 수열의 개수이고, 파란색으로 쓴 2번의 경우 뒤에서 부터 가장 긴 증가하는 부분 수열이 됩니다. 그리고 LBS는 초록색처럼 1번과 2번을 더해주되 i번째의 숫자가 두 번 들어가게 되므로 보라색처럼 -1을 하여 한 개를 빼주어야 구할 수 있습니다.

 

위 경우의 정답은 1 2 3 4 5 2 1 즉, 7이 됩니다.

---

코드

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

public class Main {
	public static int N, answer;
	public static int[] A = new int[1001];
	public static int[] memo= new int[1001];
	public static int[] memo_reverse = new int[1001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; ++i) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; ++i) {
			memo[i] = 1;
			
			for (int j = 1; j < i; ++j) {
				if (A[i] > A[j] && memo[i] < memo[j] + 1) {
					memo[i] = memo[j] + 1;
				}
			}
		}
		
		for (int i = N; i >= 1; i--) {
			memo_reverse[i] = 1;
			
			for (int j = N; j > i; j--) {
				if (A[i] > A[j] && memo_reverse[i] < memo_reverse[j] + 1) {
					memo_reverse[i] = memo_reverse[j] + 1;
				}
			}
		}
		
		for (int i = 1; i <= N; ++i) {
			answer = (answer < memo[i] + memo_reverse[i] - 1) ? memo[i] + memo_reverse[i] - 1 : answer;
		}
		
		System.out.println(answer);
	}
}

---

pyo7410/Algorithm