99클럽 코테 스터디 32일차 TIL

미들러

문제

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

#동적계획법

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

풀이

n개의 수로 이루어진 수열이 주어졌을 때 가장 긴 바이토닉 수열의 길이를 구하는 문제이다.

바이토닉 수열은 특정 수를 기점으로 증가하는 부분 수열과 감소하는 부분 수열의 길이의 합이다.

배열에 증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이를 저장한다.

1부터 n까지 요소를 탐색하며 바이토닉 수열의 길이의 최댓값을 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());

		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());

		int[][] d = new int[n][2];
		d[0][0] = 1;
		for (int i = 1; i < n; i++) {
			d[i][0] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i])
					d[i][0] = Math.max(d[i][0], d[j][0] + 1);
			}
		}

		d[n - 1][1] = 1;
		for (int i = n - 2; i >= 0; i--) {
			d[i][1] = 1;
			for (int j = i + 1; j < n; j++) {
				if (a[i] > a[j])
					d[i][1] = Math.max(d[i][1], d[j][1] + 1);
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++)
			ans = Math.max(ans, d[i][0] + d[i][1] - 1);

		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
}