최장 증가 수열(Longest Increasing Sequence)

개념 요약

• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 배열의 길이가 최대인 부분 수열이다.
• 간편한 풀이법은 DP를 이용하는 것이다.(시간 복잡도 : $O(n^2)$)
• 이분 탐색을 이용한 방법도 가능하다.(시간 복잡도 : $O(nlogn)$)

 

코드

// DP
void	LIS_DP(vector<int> &arr)
{
	// dp[i] : dp의 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이
	for (int i = 1; i < dp.size(); ++i)
	{
		// 해당 원소 초기화
		dp[i] = 1;
		// 처음부터 끝까지 루프
		for (int i j = 0; j < dp.size(); ++j)
		// 큰 값을 dp[i]에 넣는다.
			dp[i] = max(dp[i], dp[j] + 1);
    }
}

// 이분 탐색
int	binary_search(vector<int> lis, int start, int end, int element)
{
	while (start < end)
	{
		int mid = (start + end) / 2;
		if (element > lis[mid])
			start = mid + 1;
		else
			end = mid;
	}
	return (end);
}

int	LIS_BS(vector<int> &arr)
{
	int	ret = 0;
	vector<int>	list;
	list.push_back(arr[0]);
	for (int i = 1; i < n; ++i)
	{
		if (arr[i] > lis.back())
		{
			lis.push_back(arr[i]);
			ret = lis.size() - 1;
		}
		int pos = binary_search(lis, 0, ret, arr[i]);
		lis[pos] = arr[i];
	}
	return (ret + 1);
}