LIS优化

LIS(Longest Increasing Subsequence)即最长上升子序列,
如对于 3，1，5，6，2
其LIS为 3（1，5，6）

优秀博客链接：https://blog.csdn.net/zhaohaibo_/article/details/83420145

LIS

dp解决LIS时间复杂度O$(n^2)$
算法思想

  1. dp[i] 记录a[i]为末尾的上升子序列, 令0<=j < i
  2. 一重循环i遍历a[],一重循环遍历 a[0]~a[i]
    dp[i] = $\begin{cases}1,a[i]<=a[j]\ max(dp[i],dp[j]+1),a[i]>a[j]\end{cases}$

————————————————————代码如下——————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(double arr[],int n)
{
	int dp[n];
	int front[n];
	fill(dp, dp+n, 0);
	int  k, res = 0;
	for(int i = 0; i < n; ++i)
	{
		dp[i] = 1;
		for(int j = 0; j < i; ++j)
		{
			if(arr[j] < arr[i])
			{
				dp[i] = max(dp[i], dp[j]+1);
			}
		}
		res = max(res, dp[i]);
	}
	printf("%d\n", res);
}

LIS优化

队列+二分解决LIS时间复杂度O$(n log\ n)$
算法思想

  1. 队列queue动态存储上升序列，保证queue始终升序
  2. 一重循环还是i遍历a[i]，不同的是
    若a[i] 大于队列中最后一个元素，将a[i]加入队尾；
    反之，二分查找队列queue中大于a[i]的元素，令a[i]将其替换。
  3. 最后得到队列的长度即LIS

如对于 3，1，5，6，2 遍历a[i]得到的队列queue依次为：

  • 3
  • 1
  • 1，5
  • 1，5，6
  • 1，2，6

***注：
记k为序列a[0:i]的最长递增子序列的长度（$0\leq i<n$）；
queue[k]是序列a[0:i]中所有长度为k的递增子序列中的最小结尾元素值；
可以看到queue[] 并不是动态存放以a[0] ~ a[i]的LIS序列；
而是动态让升序的元素尽可能小，以便后续的更新（解释不下去了，不禁感慨队列优化算法的精妙啊~）
————————————————————代码如下——————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void solve(int arr[],int n)
{
	int queue[40005];
	int  len = 0, k, res = 0;
	queue[++len] = arr[0];
	for(int i = 1; i < n; ++i)
	{
		if(queue[len] < arr[i])
			queue[++len] = arr[i];
		else //二分查找队列queue中大于a[i]的元素
		{
			int l = 1, r = len, mid, ans;
			while(l <= r)
			{
				mid = (l + r) >> 1;
				if(queue[mid] > arr[i])
				{
					ans = mid;
					r = mid - 1;
				}
				else
					l = mid + 1;
			}
			queue[ans] = arr[i];
		}
	}

	printf("%d\n", len);
	
}

LIS题目

题目来源: https://vjudge.net/problem/HDU-1950

题目是多组样例，如果不优化O$(n^2)$的时间复杂度妥妥超时；
所以队列+二分真香啊