개념

최장 증가 부분 수열(Longest Increasing Subsequence)란, 수열에서 가장 긴 부분 수열을 의미한다.

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/vf5oiqkrpknojlj0nj0766rqb

위 수열에서 LIS는 [1, 3, 4, 7, 8]이며, 길이는 5가 될 것이다. 아래에 LIS의 길이와 LIS를 구하는 알고리즘을 서술한다.

DP - O(N²)

다이나믹 프로그래밍을 사용하여 Array의 LIS의 길이를 구하는 알고리즘은 이러하다.

LIS[i]: i번째 원소를 마지막으로 하는 LIS의 길이

LIS[i]: 0 <= j < i, Array[j] < Array[i]인 LIS[j]의 최댓값 + 1

각 원소에 대한 LIS를 구한 후 LIS의 최댓값이 최장 증가 부분 수열의 크기다.

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/mbf0mtkk9dac147medep9wr66

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/a3dbcizanr07ofraj12zk4o0f

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/9f5oc4jnc687q5cpp83kxw4pl

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/kyvnxbfmwqiaqxyrc1rtdkvxu

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/y07o6mizmt0tgdxjiwc2vdws3

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/to8ut4hfcasjj3z7fye1d56re

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/0hgv8mr654qc5ny3drjs6nv3b

https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/9rbf93m0l142z030hij0w2u1n

전체 배열을 순회하는 데에 N, 각 i마다 LIS[j]의 최댓값을 구하는 데에 한 번 더 순회하니 N이 걸리므로 알고리즘의 시간복잡도는 O(N²)다. 아래의 백준 문제를 이 알고리즘을 사용하여 해결 가능하다.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<int> arr(N);
    vector<int> lis(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        int maxVal = 0;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                maxVal = max(maxVal, lis[j]);
            }
        }
        lis[i] = maxVal + 1;
    }
    cout << *max_element(lis.begin(), lis.end());
    return 0;
}