最长上升子序列

tag: 线性DP, [二分法]

$\textbf{\textcolor{gold}{此版本为优化版}}$

题目要求: 给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

数据范围

$$1≤N≤100000， −10^9≤数列中的数≤10^9$$

思路

用一个数组 $q[\ \ \ ]$ 储存长度为 $i$ 的递增序列结尾的最小值.

记当前读到的数是 $a_i$ , 通过[[二分法]]找到 $q[\ \ \ ]$ 中第一个大于等于 $a_i$ 的数并用 $a_i$ 将其替换.

原因:

• 由于记录的子序列都是严格单调递增的, 因此接在 $a_i$ 后的数一定严格大于 $a_i$ , 并且 $q[\ \ \ ]$ 中记录的数是当前序列长度结尾数的最小值, 因此 $q[i]$ $\textcolor{cyan}{一定严格小于}$ $q[i+1]$ . 因此 $q[\ \ \ ]$ 是一个严格单调递增的数组.
• 替换第一个大于等于 $a_i$ 的数是为了使 $q[\ \ \ ]$ 每个值都是前 $i$ 个数中, 各长度结尾的最小值.

细节方面的处理

• $q[++len]=a[1]$ //初始化 $q[1]$ 因为默认的构造函数赋的值是0, 在第一个数据大于等于第二个数据且两个数据都是正数时会导致 $q[1]$ 储存了0.

代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int a[N],q[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int len=0;
    q[++len]=a[1];//初始化第一个值
    for(int i=2;i<=n;i++)//从2开始, 可以少循环一次
    {
        int l=1,r=len;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[i]<=q[mid])r=mid;
            else l=mid+1;
        }
    //如果a[i]比最长子序列的最后一个值小,说明中间有的值可以被更新.
    if(a[i]<=q[len])q[l]=a[i];
    //如果a[i]大于最长子序列的最后一个值,那么顺理成章地,把a[i]放到子序列里面
        else q[++len]=a[i];
    }
    cout<<len;
    return 0;
}

下面是根据代码逻辑我自己”优化的代码”, 我将条件前置, 使得只有满足条件才需要二分, 然而acwing显示事件加了几毫秒, 原因在于: 当第一个条件经常不成立时, 相当于我要多走一个条件判断, 根据分析, 第一个条件确实经常不成立, 因为大量数据中只有少数时候子序列会加1.

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int a[N],q[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int len=0;
    q[++len]=a[1];//初始化第一个值
    for(int i=2;i<=n;i++)
    {
        if(a[i]>q[len])
        {
            q[++len]=a[i];
            continue;
        }
        int l=1,r=len;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[i]<=q[mid])r=mid;
            else l=mid+1;
        }
        q[l]=a[i];
    }
    cout<<len;
    return 0;
}

当然好像我把标准代码的条件换了个位置, 时间却反逻辑的减少了.