E1 最长上升子序列（二分优化） • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/B3637 ↗

题目描述

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$ ，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

6
1 2 4 1 3 4

plaintext

输出 #1

plaintext

算法解析：#

LIS 最长上升子序列： $dp[i]$ 表示长度为 $i$ 的上升子序列的最小末尾值。遍历每个数 $x$ ，用二分在 $dp$ 中找第一个 $\ge x$ 的位置替换（若 $x$ 大于所有则追加）， $dp$ 的长度就是 LIS 长度。严格上升用 $lower\_bound$ ，非严格用 $upper\_bound$ 。复杂度 $O(n\log n)$ 。

Python代码实现#

import bisect
n = int(input())
b = [0] * (n + 10)
a = list(map(int, input().split()))
b[0] = int(-2e9)
len = 0
for i in range(n):
    if b[len] < a[i]:
        len += 1
        b[len] = a[i]
    else:
        b[bisect.bisect_left(b, a[i], 1, len)] = a[i]
print(len)

python

C++代码实现#

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

const int N=100010;
int n, a[N];
int len, b[N]; //记录上升子序列

int main(){
  scanf("%d", &n);
  for(int i=0; i<n; i++) scanf("%d", &a[i]);

  b[0]=-2e9;                              //哨兵
  for(int i=0; i<n; i++)
    if(b[len]<a[i]) b[++len]=a[i];        //新数大于队尾数，则插入队尾
    else *lower_bound(b,b+len,a[i])=a[i]; //替换第一个大于等于a[i]的数(贪心)

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