最长上升子序列（LIS）问题

此处我们只讨论严格单调递增的子序列求法。

前面O（n2）的算法我们省略掉，直接进入O（nlgn）算法。

方法一：dp + 树状数组

定义dp[i]：末尾数字是i时最长上升子序列

转移方程：dp[i]=max{dp[k]|k<i}+1

代码如下：

@Frosero #include <cstdio> #include <iostream> #include <cstring> #define MAXN 100010 using namespace std; int tree[MAXN*4]; int read(int pos){ int ans = 0; while(pos > 0){ ans = max(ans,tree[pos]); pos -= pos & -pos; } return ans; } void updata(int pos,int val){ while(pos < MAXN*4){ tree[pos] = max(tree[pos],val); pos += pos & -pos; } } int a[MAXN],n,dp[MAXN],ans = 0; int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); memset(tree,0,sizeof(tree)); for(int i=0;i<n;i++){ dp[a[i]] = read(a[i] - 1) + 1; updata(a[i],dp[a[i]]); ans = max(ans,dp[a[i]]); } printf("%d\n",ans); return 0; }

方法二：dp + 单调队列

定义dp[i]：末尾数字是下标为i的数字时最长上升子序列

定义单调队列g[i]：上升子序列长度为i时最后一位的最小值

代码如下：

@Frosero #include <cstdio> #include <iostream> #include <cstring> #define MAXN 100010 #define INF 0x3f3f3f3f using namespace std; int a[MAXN],n,dp[MAXN],g[MAXN],ans = 0; int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<=n;i++) g[i] = INF; for(int i=0;i<n;i++){ int k = lower_bound(g+1,g+n+1,a[i]) - g; dp[i] = k; g[k] = a[i]; ans = max(ans,k); } printf("%d\n",ans); return 0; }

方法三：单调队列

定义单调队列g[i]：上升子序列长度为i时最后一位的最小值

代码如下：

@Frosero #include <cstdio> #include <iostream> #include <cstring> #define MAXN 100010 #define INF 0x3f3f3f3f using namespace std; int a[MAXN],n,g[MAXN],ans = 0; int main(){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<=n;i++) g[i] = INF; for(int i=0;i<n;i++){ int k = lower_bound(g+1,g+n+1,a[i]) - g; g[k] = a[i]; ans = max(ans,k); } printf("%d\n",ans); return 0; }

囧，相信大家也发现了第二个算法中dp数组事实上貌似并没有什么用了吧。但事实上他在过程中为我们维护了一些信息，在某些习题中我们恰好就要利用到他们了。

还有一点就是如果我们要寻找最长单调不减子序列，上面代码只要稍微更改一下即可，请读者自己思考吧，哈哈 ^.^ 加油！

转载于:https://www.cnblogs.com/ScratchingBear/p/5345839.html