백준 11053번 자바 : 가장 긴 증가하는 부분 수열

x번째 값이 가지는 가장 긴 증가하는 부분수열의 길이를 구하고 싶다면 , 1 ~ x - 1번째 값들 중, x번째 값 보다 더 작은 숫자들이 갖는 부분수열의 길이 중, 가장 길이가 긴 부분수열의 길이에 + 1을 한 값이, x번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이이다

DP[a] = b 의 의미는 "a번째 값이 가지는 가장 긴 증가하는 부분수열의 길이는 b이다."

출처: https://yabmoons.tistory.com/516 [얍문's Coding World..:티스토리]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 
    
    static int N;
    static int[] arr, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int answer = 0;
        for(int i=0; i<N; i++) {
            if(dp[i]>answer) answer = dp[i];
        }
        System.out.println(answer);
    }


}