首页 > itarticle > lis nlogn解法

lis nlogn解法

admin 11月 13, 2020 0

$LIS$: 最长上升子序列

解法

$LIS$ 的 $well-knowed$ 的 $dp$ 解法是 $n^2$
$nlogn$解法是二分贪心替换掉当前不符合上升的数字

代码


using namespace std;
typedef long long ll;

int a[100], lis[100], cnt, n;

int ()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    cnt=0;
    lis[cnt++]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>lis[cnt-1])
            lis[cnt++]=a[i];
        else
        {
            int pos=lower_bound(lis, lis+cnt, a[i])-lis;
            lis[pos]=a[i];
        }
    }
    printf("%dn", cnt);
}