最长上升子序列 II（LIS）————二分优化

题目链接
https://www.acwing.com/problem/content/898/

思路
      这题说是dp，但是分析完之后更像贪心了，首先举个例子比如一个序列：3 1 2 1 8 5 6。（后面下标从1开始计）那么对于 $a[1]$ 和 $a[2]$来说，如果上升子序列长度为2，那么能接在 $a[1]$ 后面的也一定能接在 $a[2]$后面，因为$a[2]<a[1]$。以此思想，引出我们 $dp$ 数组 $f$ 的状态表示。
      我们的状态表示为 $f[i]$ 存放的是所有长度为 i 的上升子序列中所有末尾值中的最小值，这样就能得到一个严格的单调递增序列，我们来证明一下为什么严格单调递增，假设 $f[6]\le f[5]$，那么对于长度为6的这个上升子序列来说，它的第五个数 $t$ 一定是小于 $f[6]$的，那么就存在 $f[5]>t$ ，但是我们存放的是所有长度为5的上升子序列的末尾值中的最小值，所以矛盾了，故这个序列一定是单调递增的。那么对于 $a[i]$ 我们只需要查找 $f$ 数组中小于 $a[i]$ 的最大值 $j$ 即可，然后可以直接更新$f[j+1]=a[i]$，因为 $a[i]$一定小于当前 $f[j+1]$，不然也不会找到 $j$ 了，那么这个查找到 j 的过程就是可以运用二分查找来优化，所以整个算法的时间复杂度就由朴素做法的$O(n²)$优化到$O(nlogn)$。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int a[N];
int f[N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    f[0]=-2e9;//哨兵作用
    int len=0;

    for(int i=0;i<n;i++)
    {
        int l=0,r=len;
        while(l<r)
        {
            int mid=(l+r+1)>>1;//向上取整
            if(f[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        f[r+1]=a[i];
    }

    printf("%d\n",len);
    return 0;
}