Algorithm, boj, 가장 긴 바이토닉 부분 수열(11054)

풀이

• dp[i]는 i번째의 수가 기준이 되어 바이토닉 수열이 될때 최대의 길이 이다
• 바이토닉 수열은 S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN 를 만족 해야 하므로 기존에 증가하는 부분수열, 감소하는 부분수열의 합을 구하면 된다
• dp1[i]는 i번째 수가 가장 큰 증가하는 부분수열.
• dp2[i]는 i번째 수가 가장 큰 감소하는 부분수열.
• max는 dp1[i] + dp2[i] - 1(자기자신 중복된것 제외) 중에서 가장 큰값을 구한다.

package org.baekjoon;

import java.util.Scanner;

public class test11054_dp_Lis {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp1 = new int[n];
		int[] dp2 = new int[n];
		int max = 0;
		int[] arr = new int[n];

		for (int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
			dp1[i] = 1;
			dp2[i] = 1;
		}

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

		for (int i=0; i<n; i++) {
			max = Math.max(dp1[i] + dp2[i], max);
		}
		System.out.println(max-1);

	}

}

---

Reference

• 문제보러가기

---