nlogn的LIS（最长上升子序列）算法讲解

传统的LIS复杂度为O(n*n)每次都要寻找比当前点小的所有在它之前的点

O(nlogn)的则是每遍历到一个点，都将该点放在大于等于（大于也可以）该点value的第一个点的位置。更改该点的value而不进行移动。如果该点比数组中的最后一个点大则整个数组的长度加一。保证数组lis[i]表示的是长度为i的子序列，末尾即最后一个元素的最小值。最后数组的大小就是最长上升子序列的大小

特注此代码表示严格上升的，非严格上升条件应改为

a[i] >= lis[len - 1]
           

核心代码

for(int i = 0; i < n; i ++)
{
    if(len == 0 ||a[i] > lis[len - 1])
    {
        lis[len] = a[i];
        len ++;
    }
    else
    {
        p = lower_bound(lis,lis +len,a[i]) - lis;
        lis[p] = a[i];
    }
}

           

或者

因为该点大于lis数组中的最后一个值lower_bound的返回值就是数组的长度len

for(int i = 0; i < n; i ++)
{
    p = lower_bound(lis,lis +len,a[i]) - lis;
    lis[p] = a[i];
    if(p == len)
        len ++;
}