DP [백준 11053번 가장 긴 증가하는 부분수열] -java-

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

 

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

흔히 LIS라고 불리는 문제이다. 

 

dp[i]= numbers[i]로 끝나는 부분 수열을 의미한다. 

dp[i]는 dp[j]+1이다. 단, numbers[j] < numbers[i] && dp[i] < dp[j] + 1 일 때만 적용된다. 이유는 numbers[i]보다 numbers[j]값이 작아야 할것이며 길이도 1적은것보다 작아야 하기 때문이다.

 
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] dp = new int[num + 1];
        int[] numbers = new int[num + 1];
        for (int i = 1; i < num + 1; i++) {
            numbers[i] = sc.nextInt();
        }
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j < i; j++) {
                if (numbers[j] < numbers[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        Arrays.sort(dp);
 
        System.out.println(dp[num]);
 
    }
 
}