BOJ 11053. 가장 긴 증가하는 부분수열 (LIS)

BOJ 11053. 가장 긴 증가하는 부분수열 (LIS)

가장 긴 증가하는 부분수열(Longest Increasing Subsequece) [나무위키]

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다.
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

풀이

d[i] = a[1], …… a[i] 까지 수열이 있을 때, a[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이

예를들어 a[1], a[2], a[3], a[4] …. a[i] 라는 수열이 있을 때 

a[i]의 바로 전 수는 뭘까?
알 수없으므로 변수 j를 둔다.

a[1], a[2], a[3], a[4] …. , a[j], a[i]
j 는 i보다 작고, a[j] < a[i]일때 LIS가 된다.

점화식 d[i] = max(d[j]) + 1
j< 1 ,  a[i] > a[j]

import java.io.IOException;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] d = new int[n];
        int max = -1;

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            d[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }

            if (max < d[i]) {
                max = d[i];
            }
        }
        sc.close();
        System.out.println(max);
    }
}

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ").map { it.toInt() }
    val d = IntArray(n) { 1 }

    for (i in 0 until n) {
        for (j in 0 until i) {
            if (arr[i] > arr[j]) {
                d[i] = max(d[i], d[j] + 1)
            }
        }
    }

    println(d.maxOf { it })
}

풀이소스

github.com/beomjo/algorithm-study/commit/0b4f0b0e945e335949409e9b9968b802733704bf