[알고리즘] LIS(Longest Increasing Subsequence)

LIS(Longest Increasing Subsequence_가장 긴 증가하는 부분 수열)이란?

---

백준의 다음 문제를 가지고 LIS를 정리해보자 ---> www.acmicpc.net/problem/11053

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾아야한다.

예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

 

DP를 이용하여 풀 수 있다. DP 배열에는 해당 인덱스까지의 최대 길이를 저장한다.

 

[그림 1] 각 인덱스에 따라 DP 배열에 저장되는 값(길이)

 

먼저 첫 번째 인덱스에서는 당연히 자기 자신밖에 없기 때문에 최장 길이가 1이다.

두 번째 인덱스를 보면, 해당 값이 이전의 값보다 크기 때문에 이전 인덱스의 DP 배열의 값 + 1을 해준다.

 

[그림 2] 각 인덱스별로 DP 배열에 저장되는 값

 

 

 

코드

---

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            int[] dp = new int[N];
            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[i] <= dp[j]) {
                        dp[i] = dp[j] + 1;
                    }
                }
            }

            int max = 0;
            for (int i : dp) {
                max = Math.max(max, i);
            }
            System.out.println(max);
        } catch (Exception ex) {
            ex.getMessage();
        }
    }
}