최장 증가 부분 수열(Longest Increasing Subsequence)란, 수열에서 가장 긴 부분 수열을 의미한다.
https://potions.potions.dev/widgets/UMPyjsX3G0YKF9Q3IeTxK4ZWPR73/vf5oiqkrpknojlj0nj0766rqb
위 수열에서 LIS는 [1, 3, 4, 7, 8]이며, 길이는 5가 될 것이다. 아래에 LIS의 길이와 LIS를 구하는 알고리즘을 서술한다.
다이나믹 프로그래밍을 사용하여 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²)다. 아래의 백준 문제를 이 알고리즘을 사용하여 해결 가능하다.
#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;
}