다이나믹프로그래밍 - 가장 긴 증가하는 부분 수열

import java.util.Arrays;
import java.util.Scanner;

public class TestDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[N+1];
        int[] dp = new int[N+1];
        
        for (int i=0; i<N; i++) {
        	arr[i] = scanner.nextInt();
        }
        
        // 10, 20, 10, 30, 20, 50 
        // 10, 20, 10, 25, 20, 43
        
        dp[0] = 1;
        for (int i=1; i<N; i++) {
        	dp[i] = 1;
        	for (int j=0; j<i; j++) {
        		if(arr[i] > arr[j] && dp[j]+1 > dp[i]) {
        			dp[i] = dp[j] + 1;
        		}
        	}
        }
        Arrays.sort(dp);
        System.out.println(dp[N]);

       // OptionalInt ans = Arrays.stream(dp).max();
       // System.out.println(ans.getAsInt());
        
        scanner.close();
    }
}