[알고스팟][C++] LIS: Longest Increasing Subsequence

(출처: 종만북)

문제 링크: https://algospot.com/judge/problem/read/LIS

 

 

부분 수열(Subsequence)이란 수열에서 0개 이상의 숫자를 지우고 남은 수열을 말합니다.

부분 수열에 포함된 숫자들이 순 증가(strictly increasing)할 때 이 부분 수열을 증가 부분 수열(Increasing Subsequence)라고 합니다.

 

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

 

\[ lis(start) = S[start]\text{에서 시작하는 부분 증가 수열 중 최대 길이} \]

점화식을 이렇게 세우면 됩니다. 재귀호출때마다 S[start] 뒤에 있고 큰 수들 중 하나를 다음 숫자로 결정한 뒤, 여기서 시작하는 부분 증가 수열의 최대치를 구하면 됩니다.

코드로 쓰면 아래와 같습니다.

int n;
int cache[100], S[100];

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

	ret = 1;	// 항상 S[start]는 있으니 길이는 최하 1
	for (int next=start+1; next<n; ++next)
		if (S[start] < S[next])
			ret = max(ret, lis(next) + 1);

	return ret;
}

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

위 함수를 호출할 때는 항상 시작 위치를 지정해줘야 하니, 각 위치를 순회하면서 최대값을 찾는 코드를 만들어줘야 합니다.