最長遞增子序列（LIS）的O(NlogN)列印算法

題目：

求一個一維數組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的性質——序列是有序的（單調的），就可以用二分查找，在O(logN)的時間内完成一次替換，是以算法的複雜度是O(NlogN)的。

代碼如下：

#include<bits/stdc++.h>
using namespace std;

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

int a[mx], dp[mx], pos[mx], fa[mx];
vector<int> 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<bits/stdc++.h>
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\n", len);
	}
	return 0;
}
           

最長遞減子序列：

#include<bits/stdc++.h>
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<int>()) - lis;
			lis[j] = x;
			len = max(len, j);
		}
		printf("%d\n", len);
	}
	return 0;
}
           

附：O(N^2)算法

像LCS一樣，從後向前分析，很容易想到，第i個元素之前的最長遞增子序列的長度要麼是1（單獨成一個序列），要麼就是第i-1個元素之前的最長遞增子序列加1，這樣得到狀态方程：

        LIS[i] = max{1,LIS[k]+1}  (∀k<i，arr[i] > arr[k])

這樣arr[i]才能在arr[k]的基礎上構成一個新的遞增子序列。

代碼如下：在計算好LIS長度之後，遞歸輸出其中的一個最長遞增子序列。

#include<cstdio>
#include<algorithm>
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\n", LIS(arr, sizeof(arr) / sizeof(*arr)));
	outputLIS(arr, sizeof(arr) / sizeof(*arr) - 1);
	return 0;
}