백준 / 2565 / 가장 긴 바이토닉 부분 수열 / java

package backjun.H동적계획;

import java.util.Scanner;
import java.util.Arrays;

public class 바이토닉부분수열 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] arr = new int[n];
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];

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

                if(arr[n-j-1] > arr[n-i-1]){
                    dp2[n-j-1] = Math.max(dp2[n-j-1], dp2[n-i-1] + 1);
                }
            }
        }

        // Arrays.stream(dp1).forEach(a -> System.out.print(a + " "));
        // System.out.println();
        // Arrays.stream(dp2).forEach(a -> System.out.print(a + " "));
        // System.out.println();

        for(int i=0; i<n; i++)
            dp2[i] += dp1[i];
        
        System.out.println(Arrays.stream(dp2).max().getAsInt() - 1);
    }
}

LIS(Longest Increasing Subsequence) - 최장 증가 부분 수열 알고리즘 응용 문제

이 문제는 LIS를 위한 Dp 배열을 두개 만들어서 앞에서 부터 시작하는 LIS와 뒤에서 부터 시작하는 LIS 두개를 구한 후 두개의 LIS를 합해서 구할 수 있다.

자바 Stream을 통해 max 값을 구하고, 배열을 탐색하는 것에 대해 익숙해지는 중이다.

확실히 Stream을 사용하면 코드가 좀더 깔끔한 느낌이다.