백준 14002 가장 긴 증가하는 부분수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

N이 1000인 전형적인 DP(LIS 문제)

Math.max(현재 까지의 길이 + 1, 앞에 기록되어있는 길이)
역 추적하기 위해서 기록되어 있는 길이 중 가장 긴 길이
부터 0까지를 대조해서 계단식으로 출력해주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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());
        String st[] = br.readLine().split(" ");

        int array[] = new int[N+1];
        for(int i = 1; i <= N; i++) {
            array[i] = Integer.parseInt(st[i - 1]);
        }



        int DP[] = new int[N + 1];
        DP[1] = 1;
        for(int i = 1; i <= N; i++) {
            int p = array[i];
            for(int j = i + 1;  j <= N; j++) {
                if(p < array[j]) {
                    // 증가한다면?
                    DP[j] = Math.max(DP[j], DP[i] + 1);
                }
            }
        }
        int c = Arrays.stream(DP).max().getAsInt();
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = N; i >= 1; i--) {
            if(c == -1) {
                break;
            }
            if(DP[i] == c) {
                cnt++;
                sb.insert(0, array[i] + " ");
                c--;
            }
        }
        System.out.println(cnt);
        System.out.println(sb);
    }
}