最长上升子序列(LIS)

最长上升子序列+模板

定义

最长上升子序列（Longest Increasing Subsequence），简称LIS。还有一种最长非降子序列，其区别是LIS没有相等的数，例如1 2 3是一个最长上升子序列，而1 2 2 3是一个最长非降子序列。

对于一个序列$a_1,a_2,...,a_n$,有子序列$a_1,a_2,...,a_k$，其中 $1 \le a_1 \le a_2 \le ...\le a_k \le n$.我们称这个样一个子序列是一个上升子序列，而求出这样最长的上升子序列，便是本篇文章要学习的内容。

对于序列1 5 3 7 2 4 6，其中的上升子序列有1 5 7,1 3 7,1 3 4 6,1 2 4 6……而这些子序列中最长的有1 3 4 6和1 2 4 6，长度为4，所以该序列的最长上升子序列为4。同时可以发现最长上升子序列不唯一，一个序列可以有多个最长上升子序列，但是长度唯一。

解法

动态规划 $O(n^2)$

将复杂问题拆分成多个简单问题。

求长度为n的序列的LIS，实际上是在长度为n-1的序列上推过来的，因此可用DP求解。

**状态表示：**dp[i] 为以a[i]结尾的最长上升子序列的长度。

**状态转移：**dp[i] = max(dp[i],dp[j] + 1)，其中1 <= j < i,a[j] < a[i]。

也就是说，对于每个a[i]，每次都向前找比它小的数，然后找到以a[i]结尾的最长的子序列。

由于每次都要循环两次，因此时间复杂度为$O(n^2)$，这是一个很大的时间复杂度，在数据范围庞大的时候，此方法不适合。

CODE

for (int i = 1;i <= n;i ++) {
	dp[i] = 1;
    for (int j = 1;j < i;j ++)
        if (a[j] < a[i])
            dp[i] = max(dp[i],dp[j] + 1);
   	ans = max(ans,dp[i]);
}

---

贪心+二分 $O(nlogn)$

对于上升子序列，其结尾元素越小越有利于增长。定义一个数组f存放这个最长上升子序列，最后数组f的长度就是答案。

对于每个a[i]，如果a[i] > f[len]，则f[++ len] = a[i]；如果a[i] <= f[len]，则用a[i]更新f数组，在f数组中找到第一个大于等于a[i]的元素f[j]，用a[i]更新f[j]。由于f数组是单调递增的，所以可以使用二分来查找这个应该更新的位置，二分查找的时间复杂度为$O(logn)$，因此总的时间复杂度为$O(nlogn)$。

CODE

f[++len] = a[1];
for (int i = 2;i <= n;i ++)
	if (a[i] > f[len])	f[++ len] = a[i];
	else 	f[find(a[i])] = a[i];

其中find函数为

int find(int x) {
	int l = 1,r = len;
	while(l < r) {
		int mid = l + r >> 1;
		if (f[mid] < x) l = mid + 1;
		else r = mid;
	}
	return l;
}

lower_bound()函数

C++中可用lower_bound()函数代替二分查找第一个大于等于查找元素的位置。

f[++len] = a[1];
for (int i = 2;i <= n;i ++)
	if (a[i] > f[len])	f[++ len] = a[i];
	else {
		int idx = lower_bound(&f[1],&f[len],a[i]) - &f[0];
		f[idx] = a[i];
	}