22.3.28

1，LIS（3种解法）；

1，LIS

解法一：

dp，时间复杂度： O（n^2）；

f[ i ]表示以a[ i ]结尾的子序列长度；

边界处理f[ i ] = 1;

状态转移方程：f[ i ] = max( f[ i ] , f[ j ] + 1)

#include
#define rep1(i,a,n) for(int i=a;ia;i--) 
#define per2(i,n,a) for(int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair PII;
typedef double db;
const int N=1e3+10;
int n;
int a[N],f[N];
int main()
{
	quick_cin();
	int n;
	cin>>n;
	rep2(i,1,n)f[i]=1;
	rep2(i,1,n)cin>>a[i];
	int maxx=1;
	rep2(i,1,n)
	{
		rep2(j,1,i)
		{
			if(a[j]

解法二：

贪心+二分 时间复杂度：O（nlogn）

c++库函数居然 连二分都有，绝了；

lower_bound():返回容器中第一个值【大于或等于】val的元素的iterator位置

upper_bound():返回容器中第一个值【大于】val的元素的iterator位置

（因为返回的是 迭代器位置，所以要最后减去容器本身）

于是赶紧手动测试下；

看以看出，lower_bound() 返回的下标值挺准确的 就是第一个3出现的位置5，

但是upper_bound()返回的下标是多1的，这样理解：

它是找的插入位置，这样理解lower_bound 和 upper_bound() 函数的作用；

当然，这个模板也可以自己定义比较方案，

找最长上升子序列，我们希望开头的数尽可能的小，这样往后能够延伸的长度也越长；

新建一个 low 数组，low [ i ]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护 low 数组，对于每一个a[ i ]，如果a[ i ] > low [当前最长的LIS长度]，就把 a [ i ]接到当前最长的LIS后面，即low [++当前最长的LIS长度] = a [ i ]。 

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
const int maxn =300003, INF = 0x7f7f7f7f;
int low[maxn], a[maxn];
int n, ans;
 
int binary_search(int *a, int R, int x)
//二分查找，返回a数组中第一个>=x的位置 
{
    int L = 1, mid;
    while(L <= R)
    {
        mid = (L+R) >> 1;
        if(a[mid] <= x)
            L = mid + 1;
        else 
            R = mid - 1;
    }
    return L;
}
 
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) 
    {
        scanf("%d", &a[i]); 
        low[i] = INF;   //由于low中存的是最小值，所以low初始化为INF 
    }
    low[1] = a[1]; 
    ans = 1;   //初始时LIS长度为1 
    for(int i=2; i<=n; i++)
    {
        if(a[i] > low[ans])    //若a[i]>=low[ans]，直接把a[i]接到后面 
            low[++ans] = a[i];
        else       //否则，找到low中第一个>=a[i]的位置low[j]，用a[i]更新low[j] 
            low[binary_search(low, ans, a[i])] = a[i];
    }
    printf("%dn", ans);   //输出答案 
    return 0;
}
————————————————
版权声明：本文为CSDN博主「lxt_Lucia」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lxt_Lucia/article/details/81206439