最长上升子序列的优化算法(半成品题解,后续进行补充)
算法思想:
设置两个数组,一个a数组,一个q数组,a数组用来存储给定的数组序列,q数组用来存储最终答案的最长上升子序列,最长上升子序列一定是增序排列,q数组最开始为空,长度为len;
- 如果
q[len]>a[i]
:将满足条件的的a[i]
添加入q[len]
,执行的是q[len+1]=a[i]
; - 如果
q[len]<=a[i]
:用当前的a[i]
值替换q数组中最后的值;(???即便能保证q[len]>a[i]
,又如何保证q[len-1]>a[i]
呢?)
上述思路参考题解
在具体的实现过程中的,逐个寻找满足条件的q值比较麻烦,由于q数组的递增的数组,因此使用二分的方式来寻找满足条件的元素,在该题的判断过程中,没有执着于判断最后一个元素,由于二分算法的特殊性(必然能找到一个元素,不管这个元素与所寻找的元素是否相等,),选择寻找q数组中小于a[i]且最接近a[i]的元素;
注意事项&疑问:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int q[N],a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int len=0;
q[0]=-2e9;
for(int i=0;i<n;i++){
int l=0,r=len;
//寻找小于a[i]且最接近a[i]的数
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1);
q[r+1]=a[i];
}
cout<<len;
return 0;
}