博客

定义：

最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。假设我们有一个序列 b i，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N，但必须按照从前到后的顺序。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，我们就会得到一些上升的子序列，如(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等，而这些子序列中最长的（如子序列(1, 3, 5, 8) ），它的长度为4，因此该序列的最长上升子序列长度为4。

须知：LIS序列不一定唯一，但长度唯一，如序列（1，7，3，5，9，4，8）其LIS序列可以是1，3，5，9也可以是1，3，5，8，但长度是4

求解方法：

大致有三种方法：

dp，复杂度为O（n^2）

贪心 + 二分，复杂度为O(nlogn)

O(nlogn)的树状数组优化的DP

这里我主要介绍前两种o(≧v≦)o

动态规划

对于动态规划我们第一步应该确定状态，第一反应是把所问当作状态，也就是dp[i]表示前i个数的最长上升子序列的长度，但是当你处理子问题的时候要考虑该点要不要插入数组，就得与当前LIS的最后一项进行比较，问题来了，当前LIS的最后一项是什么？？？这就是历史遗留问题，不满足无后效性，所以得转换状态o(︶︿︶)o

既然不知道每个数选不选，那我们的状态dp[i]就考虑为以第i个数为结尾的最长LIS序列的长度

状态转移方程：


f[i] = max{f[j] + 1},tr[j] <= tr[i]，j < i


边界处理：


dp[i] = 1


实现过程是对每个数i，从头扫到i – 1，去找小于等于tr[i]的最大的dp值，此时dp[i] = dp[j] + 1

最后扫一遍循环，去找最大值

两层for循环，所以是O（n^2）

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, dp[MAX], tr[MAX];

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i)scanf("%d",&tr[i]);
    for(int i = 1; i <= n; ++i){
        dp[i] = 1;
        for(int j = 1; j < i; ++j){
            if(tr[i] >= tr[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    m = 1;
    for(int i = 1; i <= n; ++i){
        m = max(dp[i], m);
    }
    cout<<m<<endl;   
    return 0;
}

贪心+二分

所谓贪心，就是往死里贪，所以对于最大上升子序列，结尾元素越小，越有利于后面接上其他的数，也就可能变得更长

所以贪心的做法是，建立一个dp数组,dp[i[表示长度为i的LIS结尾元素的最小值，因此我们只需要维护dp数组即可

对于每一个数组的数，我们对他们进行判断，如果他大于等于dp[ans]的值，就把他放在数组后面，dp[++ans] = tr[i]，否则，就在dp中去找大一个大于等于他的位置pos，dp[pos] = tr[i]。如果从头扫一遍数组，时间复杂度还是O（n^2），这与曹贼何异？！通过观察我们知道，这次维护的dp数组是单调递增的，所以就可以使出秘技二分之lower_bound来找pos的位置

我们举个栗子🌰：

• tr[] = 2 5 18 3 4 7 10 9 11 8 15
• dp[1] = 2;
• 5大于2，所以dp[2] = 5
• 18大于5，所以dp[3] = 18
• 3小于18，所以二分去找，pos是2，所以dp[2] = 3
• 4小于18，所以二分去找，pos是3，所以dp[3] = 4
• 7大于4，所以dp[4] = 7
• 10大于7，所以dp[5] = 10
• 9小于10，所以二分去找，pos是5，dp[5] = 9
• 11大于9，所以dp[6] = 11
• 8小于11，所以二分去找，pos是5，dp[5] = 8
• 15大于11，所以dp[7] = 15

所以最长上升子序列的长度为7

注意：dp数组得到的不一定是真正的LIS

比如：tr[] = 1 4 7 2 5 9 10 3

得到的是1 2 3 9 10，而真正的LIS是1 2 5 9 10

因此dp数组得到的不一定是真正的LIS，他只表示最长子序列长度的排好序的最小序列，对于最后一半将5换成3的意义是记录最小序列，便于后续数据的处理

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, dp[MAX], tr[MAX], ans;

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i)scanf("%d",&tr[i]);
    dp[1] = tr[1];
    ans = 1;
    for(int i = 2; i <= n; ++i){
        if(dp[ans] <= tr[i]){
            dp[++ans] = tr[i];
        }
        else{
            dp[lower_bound(dp + 1, dp + 1 + ans, tr[i]) - dp] = tr[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

介绍一个新的方法，是针对所有的数都不同的情况，和二分的差不多，不过好写一点

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define NMAX 1000 + 50
#define MAX 100000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x;
int tr[MAX];
bool vis[MAX];

void work(){
    sd(n);
    set<int>se;
    set<int>::iterator it;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        it = se.lower_bound(x);
        if(it != se.end()){
            se.erase(it);
            se.insert(x);
        }
        else se.insert(x);
    }
    cout<<se.size()<<endl;
    
}


int main(){
//    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

写在最后

树状数组维护的方法我懒得学⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄（我一定会回来滴！

想起来第一次做这个LIS是为了打上海站而刷VJ的时候遇到了，当时我就是直接贪心，不过我忘了怎么贪的了，反正wa了，好像也没管，时隔三个月才补（惭愧惭愧.jpg

还有，我居然被催更了？？？？？(>_<)