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

 

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

 

문제 접근 과정

 바이토닉 수열의 정의

• 먼저 증가하다가 그 이후 감소하는 수열.
• 예시: [1, 3, 5, 4, 2]

각 위치를 기준으로 생각할 때,

• 왼쪽에서 오른쪽으로 봤을 때 증가 수열의 길이를 구함.
• 오른쪽에서 왼쪽으로 감소하는 수열의 길이를 따로 구함.
• 그 후 두 결과를 합치면 바이토닉 수열이 됩니다.

DP 정의 방법

• increase[i] : i번째 수가 마지막인 증가하는 수열 중 가장 긴 길이
• decrease[i] : i번째 수가 처음인 감소하는 수열 중 가장 긴 길이
• increase: 왼쪽→오른쪽 방향으로 증가 수열 길이
• decrease : 오른쪽→왼쪽 방향으로 감소 수열 길이

점화식

increase[i] = Math.max(increase[i], increase[j] + 1); // 단, j < i이고 array[j] < array[i]
decrease[i] = Math.max(decrease[i], decrease[j] + 1); // 단, j > i이고 array[j] < array[i]

최종 결과 계산

 

각 위치를 기준으로 두 dp 값을 더하고, 중복된 자기 자신(i)은 하나 빼줌.

answer = max(increase[i] + decrease[i] - 1) for 0 <= i < n

 

코드

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

public class Main {    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] array = new int[n];
		int[] increase = new int[n];
		int[] decrease = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(st.nextToken());
			increase[i] = 1;
			decrease[i] = 1;
		}
		
		int maxLength = 1;
		
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                	increase[i] = Math.max(increase[i], increase[j] + 1);
                }
            }
        }


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

        for (int i = 0; i < n; i++) {
            maxLength = Math.max(maxLength, increase[i] + decrease[i] - 1);
        }

		
		System.out.println(maxLength);
	}
}