最长上升子序列(LIS)问题
此处我们只讨论严格单调递增的子序列求法。
前面O(n2)的算法我们省略掉,直接进入O(nlgn)算法。
方法一:dp + 树状数组
代码如下:
@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 + 单调队列
代码如下:
@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;
}
方法三:单调队列
代码如下:
@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数组事实上貌似并没有什么用了吧。但事实上他在过程中为我们维护了一些信息,在某些习题中我们恰好就要利用到他们了。
还有一点就是如果我们要寻找最长单调不减子序列,上面代码只要稍微更改一下即可,请读者自己思考吧,哈哈 ^.^ 加油!