가장 긴 증가하는 부분 수열 4

문제 링크

발상 & 점화식

문제는 경로 추적을 제외하면 가장 긴 증가하는 부분 수열과 동일하다. 이전 문제와 같이 1차원 문제이기 때문에 추적도 같은 방식으로 이전 최적 인덱스를 페어로 저장하는 방식으로 진행할 수 있다.

$$\{\begin{array}{l}{n}_i=\text{인덱스 i로 끝나는 가장 긴 LIS 길이}\\ a_i=\text{i번째 수}\end{array}$$ $$n_i=\underset{k=1\to i-1}{\max }(\{\begin{array}{ll}{n}_k& \text{if ai>ak}\\ 0& \text{else}\end{array})+1$$

역추적

위 점화식에서 $n_i$마다 최댓값이 뽑힌 인덱스 $k$도 같이 저장하면 경로를 추적할 수 있다. 다만 LIS 문제 특성상 이전 문제와 똑같이 추적하면 경로가 역순으로 뽑히게 된다. 그래서 이번에는 재귀호출을 이용해 경로를 추적하는 것이 코드가 깔끔하다. 물론 이전 문제처럼 경로를 알아내고 배열에 저장한 다음에 뒤집어 출력할 수도 있지만 이렇게 하는게 더 코드가 깔끔하다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
	int c = 1, p = -1;
};
bool cmp(node a, node b) {
	return a.c < b.c;
}
void printlis(int x, vector<node>& pl, vector<int>& arr) {
	if (pl[x].p == -1) { // 이전 항목이 없다면 LIS 시작 요소임
		cout << arr[x] << " ";
		return;
	}
	printlis(pl[x].p, pl, arr); // 이전 LIS 요소 탐색 
	cout << arr[x] << " "; // 탐색이 끝나면 출력 ( 스택처럼 역순 출력 )
}
int main() {
	int n; cin >> n; vector<int> arr(n); vector<node> dp(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < n; i++) {
		node p;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && p.c < dp[j].c + 1) {
				p.c = dp[j].c + 1;
				p.p = j; // 현재 인덱스 이전의 마지막 LIS 인덱스 저장
			}
		}
		dp[i] = p;
	}
	auto mx = max_element(dp.begin(), dp.end(), cmp); // LIS 마지막 요소 탐색
	cout << (*mx).c << "\n"; // LIS 길이 출력
	printlis(mx - dp.begin(), dp, arr); // LIS 출력
}