백준|11053번|가장 긴 증가하는 부분 수열

문제설명
N개의 수열을 입력받고 그 수들로 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다.

작동 순서
1. 배열의 길이 N을 입력받습니다.
2. 수열의 수들을 입력받고 저장합니다.
3. 각 수의 앞에 있는 자신보다 작은 숫자들만 포함되어 있고 가장 긴 부분 수열의 길이를 가져와서 거기에 +1을 해서 저장합니다.
4. 연산이 모두 끝나면 저장된 부분수열들의 길이 중 가장 긴 길이를 출력합니다.

소스코드

import java.io.*;
import java.util.*;

public class 백준_11053번_가장긴증가하는부분수열 {
    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];
        int[] dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) arr[i]=Integer.parseInt(st.nextToken());

        dp[0]=1;

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

        int max=0;
        for(int i=0;i<N;i++) max=Math.max(max, dp[i]);
        System.out.print(max);
    }
}