최대 증가 부분 수열(LIS)

주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제입니다. 이 문제를 최대 증가 부분 수열(LIS, Longest Increasing Subsequence) 찾기 문제라고 부르며, 이는 매우 유명한 Dynamic Programming 연습 문제 중 하나입니다.

예를 들어, ‘1 2 4’는 ‘1 5 2 4 7’의 부분 수열입니다. 부분 수열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부릅니다. 그리고 ‘1 6 2 5 7 3 5 6’ 수열에서 최대 증가 부분 수열은 ‘1 2 3 5 6’입니다.

lis(start) = arr[start]에서 시작하는 부분 증가 수열 중 최대의 길이

재귀 호출할 때마다 arr[start]보다 뒤에 있고 큰 수들 중 하나를 다음 숫자로 결정한 뒤, 여기서 시작하는 부분 증가 수열의 최대치를 구하면 됩니다.

이 코드는 총 O(n)개의 부분 문제를 갖고, 하나를 해결할 때마다 O(n) 시간의 반복문을 순회하므로 전체 O(n^2) 시간 복잡도를 갑습니다.

int length;
int arr[100], cache[100];

// arr[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환
int lis(int start) {
    int &ret = cache[start];
    if (ret > 0) return ret;

    ret = 1;
    for (int next = start + 1; next < length; ++next) {
        if (arr[start] < arr[next]) {
            ret = max(ret, lis(next) + 1);
        }
    }
    return ret;
}

시작 위치 고정하기

lis()를 호출할 때는 항상 증가 부분 수열의 시작 위치를 지정해 줘야 하므로, 처음에 호출할 때 각 위치를 순회하면서 최대 값을 찾는 다음과 같은 형태의 코드를 작성해야 합니다.

int maxValue = 0;
for (int begin = 0; begin < length; ++begin) {
    maxValue = max(maxValue, lis(begin));
}