求最长上升子序列

太简单了不想写。。。。。

求其最长长度的方案数

第一种，复杂度为\(n^2\)的方法

再开一个和f[][]数组长得差不多的g[][]数组，f[][]是放长度的，g[][]是放方案数的
先看看代码

for(int i=1;i<=n;i++){
		f[i]=1;g[i]=1;
		for(int j=1;j<i;j++){
			if(a[j] < a[i]){
				int l=f[j]+1;
				if(l == f[i])	g[i] += g[j]; 
				if(l > f[i]){
					g[i]=g[j];
					f[i]=l; 
				}
			}
		}
	}

我们从第j个数转移到第i个数，
如果\(f_{[j]} + 1\) 要大于\(f_{[i]}\),那他很优秀地把\(f_{[i]}\)更新成了\(f_{[j]} + 1\),把\(g_{[i]}\)更新成了\(g_{[j]} + 1\);
如果\(f_{[j]} + 1\) 和 \(f_{f[i]}\)相等，那么\(f_{[i]}\)还是\(f{[i]}\),不过方案数就要增加了，\(g_{[i]}\)要加上\(g_{[j]}\);
如果f[j]+1要小于f[i]，那就不管他（很显然这里只有两个if，没他的份）
然后以上两个if还可以这样写：

if(l > f[i]){
	f[i]=l;g[i]=0;
}
if(f[i]==l){    
	g[i]+=g[j];
}

对了，还有输出其中一种方案的话

可以加一个pre[]数组，记录当前最长序列的上一个数是几，也就是更新\(f_{[i]}\)时，记下来\(pre_{[i]} = j\)
输出时，我们要找的就是那个\(f_{[i]}\)等于答案的i,输出\(a_{[i]}\)然后顺藤摸瓜追根溯源输出\(a_{pre_{[i]}}\),然后是\(a_{pre_{[pre_{[i]}]}}\)...

第二种，更快的方法复杂度为\(nlog^n\)(其实是如果序列里的最大值和n一个级别的话才是nlogn,本来是\(O{nlogm(m=max(a_{[1]},a_{[2]},...))}\)

前方高能，注意，是线段树！
对于\(a_{[i]}\),我们要找的是\(a_{[j]}\)比他小，并且\(f_{[j]}\)最长的这个\(a_{[j]}\)
我们要求区间最值了
搞一个线段树，搞一个\(m=max{a1,a2,a3...an}\),m是所有数的最大值，线段树区间下标是1~m，也就是以a[]做下标
线段树的区间里存的是最长上升序列的长度，即leaf[a[i]]=fi
然后我们一步步的循环1~n，对于a[i],我们要找到比他小的a[j],并且是要f[j]最大的。
我们单点查询1~a[i]-1（这些都满足a[j]<a[i]虽然不一定有这么一个a[j]）运用线段树，在logm的时间里搞出一个最大的\(f_{[j]}\),拿他加1作为\(f_{[i]}\)。
又臭又长的线段树虽然别的不会但是单点查询还是能写的呜呜

【题解】LIS（longest increasing subsequence）最长上升子序列

原文：https://www.cnblogs.com/ZhengkunJia/p/12609778.html