[11053번] 가장 긴 증가하는 부분 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main { 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar = new int[n+1];
        int[] dp = new int[n+1];
        for(int i=1;i<=n;i++){
            ar[i] = sc.nextInt();
//            System.out.print(ar[i]+" ");
        }
        
        for(int i=1;i<=n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(ar[i]>ar[j]&&dp[j]+1>dp[i]){
                    dp[i] = dp[j]+1;
                }
            }
        }
        int max = 0;
        for(int i=0;i<=n;i++){
            max = (dp[i]>max)?dp[i]:max;
        }
        System.out.println(max);        
    }
}