가장 긴 바이토닉 부분 수열

문제 정보

• 백준 골드 4
• DP
• 문제 링크

풀이

LIS를 구했을 땐, 현재 값보다 작은 수의 개수를 셌었다.¹

이번엔 작은 것 뿐만 아니라 큰 것도 세어야 한다. 수열의 크기 $N$이 최대 1,000이므로, 이중 for문을 써도 무방하다.

• $S_1<S_2<S_3<\cdots <S_k$ ← LIS
• $S_k>S_{k+1}>S_{k+2}>\cdots >S_n$ ← LDS (LIS 역순)

LIS와 LDS 모두 자기 자신($S_k$)이 포함되므로 1을 빼야 한다.

코드

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[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        
        int[] LIS = new int[n];
        for (int i = 0; i < n; i++) {
            LIS[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j])
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
            }
        }
        
        int[] LDS = new int[n];
        for (int i = n - 1; i > -1; i--) {
            LDS[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (arr[i] > arr[j])
                    LDS[i] = Math.max(LDS[i], LDS[j] + 1);
            }
        }
        
        int answer = -1;
        for (int i = 0; i < n; i++) {
            answer = Math.max(answer, LIS[i] + LDS[i] - 1);
        }
        
        System.out.println(answer);
    }
}

관련 노트

• 20260210 가장 긴 증가하는 부분 수열

Footnotes

1. 20260210 가장 긴 증가하는 부분 수열 참고. ↩