题目描述
本题与最长上升子序列Ⅰ的差距在于数据范围的变化 纯暴力的话时间复杂度是n^2的
这里显然会超时
所以需要一个优化方案
那么那些地方可以优化呢?
eg: 3 1 2 5 1 8 5 6
以3为结尾时候,最长上升子序列为1
以第一个1为结尾,最长上升子序列也是1
但是1的适用范围显然比3更广,能接到3后面的一定可以接到1后面
所以3就没必要存了。
同理 对于第二个1 2 5序列长度为2, 2 1的序列长度也为2
但是显然2 1的适用范围更广 所以2 5是废案
以此类推
即:若当前求到了第i个数, 我们可以把此前的所有上升子序列按长度划分
然后保证某一长度的上升子序列 结尾的数一定是能取得的最小数.
就像刚的例子: 一定是取2 1 而不是2 5;
这样做的好处是什么呢? 此时i之前以长度划分的子序列的末尾元素一定是递增的-----------即出现了单调递增!!
—因为前面已经保证了每个长度下,子序列的末尾是最小值,所以长度为3的子序列的末尾元素一定比长度为2的末尾要大!
我们把第i个元素之前的所有长度下的子序列的最小末尾存到q[i]中—这个末尾是实时更新的
因为有单调递增了, 我们可以通过二分写。 通过二分,查找q中第一个<当前的第i个元素a[i]的元素位置q[j]。
说明此时元素a[i]满足成为j长度下子序列的最小结尾。
—把a[i]放进来后,即序列长度变成了j+1,所以要更新q[j+1]的数据
因为通过二分确定了 a[i]一定是<q[j+1]的 所以更新q[j+1] q[j+1]= a[i]
因此,当a[i]遍历完的后,
即a[i]的值一定在q里面查入过一次了,此时q里面存的是(遍历完a后得到的)每个长度下,子序列结尾的最小值 (递增的)
即q中长度最长的就是所求的最长子序列的长度.
Q:那么q的长度到底是怎么变化的呢?
A: 如果此时q中的最长长度为4,插入的a[i]在长度<3的位置, 那么长度是就不变的 即len=len
而如果二分后得到的位置mid=4,即最后把a[i]加进来后得到的最终长度就是5 即len=mid+1;
综上 len=max(len,mid+1);
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100000+10;
int n;
int a[N];
int q[N]; //不同长度下最长上升子序列的最小结尾------这个值是严格单调递增的
//因为q是单调递增的, 所以可以对q二分找第一个<a[i]的数, 然后此时a[i]可以加到
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int len=0; //最大长度 ---q的元素个数
for(int i=0;i<n;i++)
{
int l=0,r=len; //二分区间是q的长度, ---或者说设个哨兵位,防止二分不到元素。
while(l<r) //二分出第一个<a[i]的最大的数,然后放到q中比较
{
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1); //len取最大值
q[r+1]=a[i];
}
printf("%d\n", len); //最终q的len记录的就是最长长度
return 0;
}