[BOJ] 백준 [11054] 가장 긴 바이토닉 부분 수열 JAVA

문제

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

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

풀이

증가하는 수열 -> 감소하는 수열 형태로 나오기때문에 lis 알고리즘을 일단 떠올려야 한다.
왼쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP1
오른쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP2

for 문으로 0~수열의길이 까지 순회하여 
DP1[i]+DP2[i]-1 이 가장 큰 값이 정답

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
 
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[] list = Arrays.stream(br.readLine().split(" ")).
                mapToInt(Integer::parseInt).toArray();
        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
 
        for (int i = 0; i < n; i++) {
            dp1[i] = 1;
            for (int j = 0; j < i; j++)
                if (list[i] > list[j] && dp1[i] < dp1[j] + 1)
                    dp1[i] = dp1[j] + 1;
        }
 
        for (int i = n - 1; i >= 0; i--) {
            dp2[i] = 1;
            for (int j = n - 1; j > i; j--)
                if (list[i] > list[j] && dp2[i] < dp2[j] + 1)
                    dp2[i] = dp2[j] + 1;
        }
 
        int max = dp1[0] + dp2[0] - 1;
        for (int i = 0; i < n; i++)
            max = Math.max(max, dp1[i] + dp2[i] - 1);
        System.out.println(max);
    }
}