최 장 서브 시퀀스 (LIS) 의 O (NLogN) 인쇄 알고리즘

제목:
1 차원 배열 arr [n] 에서 가장 긴 증자 서열 의 길 이 를 구 합 니 다. 예 를 들 어 서열 1, 5, 8, 3, 6, 7 에서 가장 긴 증자 서열 의 길 이 는 4 (즉 1, 3, 6, 7) 입 니 다.
LIS 는 O (NLogN) 로 도 인쇄 할 수 있 기 때문에 O (N ^ 2) 의 DP 방법 은 마지막 에 보 입 니 다.
LIS 의 성질 에서 출발 하여 더 긴 상승 서열 을 얻 으 려 면 이 서열 앞의 수 는 가능 한 한 작 아야 한다.
원 서열 1, 5, 8, 3, 6, 7 에 있어 서 하위 서열 이 1, 5, 8 일 때 3 을 만 났 을 때 서열 은 더 이상 길 어 질 수 없다.그러나 우 리 는 교 체 를 통 해 '전체 서열' 을 더욱 작 게 보이 고 더 큰 기 회 를 가 질 수 있다.이렇게 하면 교체 5 - 3 과 교체 8 - 6 이 완 료 된 후에 (이때 서열 은 1, 3, 6) 우 리 는 서열 끝 에 7 을 추가 할 수 있다.
그런데 왜 복잡 도가 O (NLogN) 일 수 있 습 니까?
관건 은 '교체' 단계 에 있 습 니 다. 시퀀스 를 직접 옮 겨 다 니 면 매번 교체 할 때마다 O (N) 의 시간 이 필요 합 니 다.그러나 우리 가 LIS 의 성질 인 서열 이 질서 가 있 는 것 (단조 로 운 것) 을 다시 이용 하면 2 분 으로 찾 을 수 있 고 O (logN) 의 시간 안에 한 번 의 교 체 를 완성 할 수 있 기 때문에 알고리즘 의 복잡 도 는 O (NLogN) 이다.
코드 는 다음 과 같 습 니 다:

#include
using namespace std;

const int inf = 0x3f3f3f3f;
const int mx = int(1e5) + 5;

int a[mx], dp[mx], pos[mx], fa[mx];
vector ans;

int get_lis(int n)
{
	memset(dp, 0x3f, sizeof(dp));
	pos[0] = -1;
	int i, lpos;
	for (i = 0; i < n; ++i)
	{
		dp[lpos = (lower_bound(dp, dp + n, a[i]) - dp)] = a[i];
		pos[lpos] = i; /// *    
		fa[i] = (lpos ? pos[lpos - 1] : -1);
	}
	n = lower_bound(dp, dp + n, inf) - dp;
	for (i = pos[n - 1]; ~fa[i]; i = fa[i]) ans.push_back(a[i]);
	ans.push_back(a[i]); ///       ans  
	return n;
}

예제:
POJ 3903 Stock Exchange
UVA 481 What Goes Up
홍보: 가중치 의 최 장 상승 서브 시퀀스:
UVa 11790 Murcia's Skyline
HDU 1087 Super Jumping! Jumping! Jumping!
다른: 최 장 하강 하지 않 는 하위 시퀀스:

#include
using namespace std;
const int mx = 10005;

int lis[mx];

bool cmp(int a, int b)
{
	return a <= b;
}

int main()
{
	int N, len, i, j, x;
	while (~scanf("%d", &N))
	{
		len = 0;
		for (i = 1; i <= N; ++i)
		{
			scanf("%d", &x);
			j = lower_bound(lis + 1, lis + len + 1, x, cmp) - lis;
			lis[j] = x;
			len = max(len, j);
		}
		printf("%d
", len);
	}
	return 0;
}

최 장 체감 서브 시퀀스:

#include
using namespace std;
const int mx = 10005;

int lis[mx];

int main()
{
	int N, len, i, j, x;
	while (~scanf("%d", &N))
	{
		len = 0;
		for (i = 1; i <= N; ++i)
		{
			scanf("%d", &x);
			j = lower_bound(lis + 1, lis + len + 1, x, greater()) - lis;
			lis[j] = x;
			len = max(len, j);
		}
		printf("%d
", len);
	}
	return 0;
}

첨부: O (N ^ 2) 알고리즘
LCS 처럼 뒤에서 앞으로 분석 하면 i 번 요소 이전의 최 장 증자 서열 의 길 이 는 1 (단독 적 으로 하나의 서열 로) 이거 나 i - 1 번 요소 이전의 최 장 증자 서열 에 1 을 더 하면 상태 방정식 을 얻 을 수 있다.
        LIS[i] = max{1,LIS[k]+1}  (∀k arr[k])
이렇게 해야만 arr [i] 는 arr [k] 를 바탕 으로 새로운 증가 서브 서열 을 구성 할 수 있다.
코드 는 다음 과 같 습 니 다. LIS 길 이 를 계산 한 후에 재 귀적 으로 출력 하 는 가장 긴 서브 시퀀스 입 니 다.

#include
#include
using namespace std;

int dp[31]; /* dp[i]   [0,i]   LIS */
int lis = 1;    /* LIS  ，    1 */

int LIS(int *arr, int arrsize)
{
	for (int i = 0; i < arrsize; ++i)
	{
		dp[i] = 1;
		for (int j = 0; j < i; ++j) ///   i         
			if (arr[j] < arr[i])
				dp[i] = max(dp[i], dp[j] + 1);
		lis = max(lis, dp[i]);
	}
	return lis;
}

/*     LIS，    dp    “  ”   */
void outputLIS(int *arr, int index)
{
	bool isLIS = false;
	if (index < 0 || lis == 0)
		return;
	if (dp[index] == lis)
	{
		--lis;
		isLIS = true;
	}
	outputLIS(arr, --index);
	if (isLIS)
		printf("%d ", arr[index + 1]);
}

int main(void)
{
	int arr[] = {1, 5, 8, 3, 6, 7};
	printf("%d
", LIS(arr, sizeof(arr) / sizeof(*arr)));
	outputLIS(arr, sizeof(arr) / sizeof(*arr) - 1);
	return 0;
}