[백준 11053번] LIS(최장 증가 부분 수열) DP

문제 링크: 11053번 가장 긴 증가하는 부분 수열

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

 

dp[i]는 arr[0~i]에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 저장한다. 그렇다면 이 dp[n]을 어떻게 갱신하느냐가 관건인데, O(n^2)의 알고리즘은 그다지 어렵지 않다. dp[n]을 구할 때, j는 0부터 n-1까지 탐색하면서 arr[i]와 arr[j]를 비교한다. 이 때 arr[i]가 더 크다면, dp[i] 즉 arr[0~i]에서 LIS의 길이는 dp[j]보다 최소한 1만큼은 더 크다. 왜냐하면 arr[i]는 arr[0~j]의 모든 수보다 더 크기 때문에 arr[0~j]에서의 LIS의 맨 마지막 원소에 arr[i]가 덧붙을 수 있는 것이다. 하지만 이는 '최소한'의 개념일 뿐이다. arr[j_1]과 arr[j_2]에 의해서 dp[i]가 두 번 갱신되었을 때를 고려해보면 dp[j_1]+1이 dp[j_2]+1보다 클 수도 있다. 이는 dp[i] = max(dp[i], dp[j]+1)을 설명해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];
        int[] dp = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
                if (arr[i] > arr[j])
                    dp[i] = Integer.max(dp[i], dp[j]+1);
        }

        int maxLen = -1;
        for (int i = 0; i < n; i++)
            if (dp[i] > maxLen)
                maxLen = dp[i];

        System.out.print(maxLen);
    }
}