가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

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

package dp;

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

public class bj_가장긴증가하는부분수열_11053 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int[] arr=new int[N];//입력 받을 배열
		int[] dp=new int[N];//각 배열의 수를 증가하는만큼 세어줄 배열
		for (int i = 0; i < N; i++) {
			arr[i]=sc.nextInt();
		}
		//입력 끝
		Arrays.fill(dp, 1);//배열을 전부 다 1로 채워줌
		//1로 채워주는 이유 : 기본 값이 자기 자신을 포함하는 1이기 때문에
		//자기 보다 뒤에 값들이 다 작다고 해도 자기 자신을 포함하기 때문에 1을 기본값으로 설정
		int max=0;
		
		//각 숫자들을 처음부터 끝까지 돌 반복문
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i]>arr[j]) dp[i]=Math.max(dp[i], dp[j]+1);
				//여기가 제일 중요
				//각 숫자를 처음부터 비교하며 숫자가 비교하는 숫자보다 크다면
				//그 dp값을 그 전에 dp값중에 가장 큰 값에 1을 더한것과 비교하여
				//더 큰 값을 지금의 dp값으로 정해준다.
				
				//처음에 헷갈렸던 점 : if문을 i가 큰 것이 아닌 j가 큰것으로 생각하고 풀었더니
				//생각했던대로 되지 않았다. i로 바꾸고 배열의 값들을 비교하며 dp값을 바꿔줘야된다는 걸 알고
				//if문을 j가 크다에서 i가 크다로 바꿔 위에 풀이법대로 그 전에 배열의 값들 중 가장 큰
				//dp배열의 값에 하나를 더한 값과 비교하여 더해주게 로직을 짜주면 된다.
			}
		}
		for (int i = 0; i < dp.length; i++) {
			if (max<dp[i]) {
				max=dp[i];
			}
		}
		System.out.println(max);
	}
}

dp너무 어렵다..