[알고리즘/C++] 최장증가부분수열구하기

최장증가 부분수열이란 수열이 주어졌을 때, 원소가 차례로 증가하는 부분 원소들을 말한다. 

 

예를 들어 2 6 1 5 7 8 4 9 라는 수열이 있으면 

 

증가하는 부분 배열의 예시들은 다음과 같다. 

 

2 6 1 5 7 8 4 9 

 

2 6 1 5 7 8 4 9

 

2 6 1 5 7 8 4 9

 

위의 3가지 예시에서 가장 길이가 긴 케이스는 1번과 2번 케이스로 5의 길이를 가진다. 

 

가장 길이가 긴 케이스를 찾는 알고리즘을 동적 계획법으로 해결해보자.

 

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

vi longestIncreasingSubseq(vi arr) {
	vi leng(arr.size(), 0);
	//벡터 초기화

	for (int k = 0; k < arr.size(); k++) {
		leng[k] = 1;
		for (int i = 0; i < k; i++) {
			if (arr[i] < arr[k]) {
				leng[k] = max(leng[k], leng[i] + 1);
			}
		}
	}
	return leng;
}

leng이라는 이름을 갖는 벡터는 특정 인덱스에서 끝나는 부분배열에서 증가되는 부분배열의 길이를 나타낸다. 

 

예를 들어 1, 2, 3, 2, 1, 6, 7, 5, 10의 케이스에서 leng[5]는 1, 2, 3, 2, 1, 6의 부분배열에서 증가되는 부분의 

 

길이 정보를 갖는다. 1, 2, 3, 2, 1, 6 따라서 leng[5]는 4이다. 

 

증가하는 부분에 대해서는 가장 마지막 원소를 반드시 포함해서 고려해야하는데 

 

leng[3]의 경우 1, 2, 3, 2의 부분 배열에서는1, 2, 3, 2 로 최장 증가 부분수열의 길이는 2이다. 

 

이런 식으로 배열을 가장 첫번째 원소부터 시작하여 부분배열에 원소를 하나씩 추가할 경우에 

 

증가되는 배열이 생성되는지 살펴보고 가능하다면 이전 케이스에서 1을 증가시킨다.

	vi arr = { 1, 2, 3, 2, 1, 6, 7, 5, 10 };
	vi length = longestIncreasingSubseq(arr);
	printVector(length);

length에 담긴 각 부분배열의 증가부분배열 길이 정보는 다음과 같다. 

1 2 3 2 1 4 5 4 6

	cout << "max value: " << *max_element(length.begin(), length.end()) << "\n";
	cout << "argmax index: " << max_element(length.begin(), length.end()) - length.begin() << "\n";

length 벡터에서 가장 큰 원소와 그 인덱스를 살펴본다. 

max value: 6
argmax index: 8

최장 증가 부분 배열의 길이는 6이며 그 부분 배열이 완성되는 인덱스는 8이다.