[1965번] 상자넣기

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];
        int[] dp = new int[n];
        for(int i=0;i<n;i++){
            ar[i] = sc.nextInt();
        }
         
        for(int i=0;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++){
            if(max<dp[i]) max = dp[i];
        }
        System.out.println(max);
    }
}