最长上升子序列

发布于 2023-03-13 | 分类于最长上升子序列、动态规划、 oi | 3分钟 | 448字数 | 浏览量：

题目描述

对于一个整数序列 $A =(a_1, a_2,\ldots , a_k)$ ，定义 $A$ 的子序列为：从 $A$ 中删除若干个元素后（允许不删，也允许将所有 $k$ 个元素都删除），剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增，则称它为 $A$ 的一个上升子序列。其中包含元素数量最多的上升子序列称为 $A$ 的最长上升子序列。例如， $(2, 4, 5, 6)$ 和 $(1, 4, 5, 6)$ 都是 $(2, 1, 1, 4, 7, 5, 6)$ 的最长上升子序列，长度都为 $4$ 。

那么，给定一个序列 $A =(a_1, a_2,\ldots , a_n)$ ，求 $A$ 的最长上升子序列的长度

输入格式

第一行一个整数 $n$ ，代表序列 $A$ 的长度

第二行是 $n$ 个由空格隔开的整数，代表 $a_1, a_2,\ldots , a_n$

输出格式

一个整数，代表最长上升子序列的长度

测试样例

样例输入

7
2 1 1 4 7 5 6

样例输出

数据规模

对于 $100\%$ 的数据， $1 \le n \le 10^6, 1\le a_i \le10^6$

#include <bits/stdc++.h>
using namespace std;
#define N 1000002
int n, a[N + 1], l[N];

int lis() {
    l[0] = a[0];
    int len = 1;
    for (int i = 1; i < n; ++i) {
        if (l[len - 1] < a[i])
            l[len++] = a[i];
        else
            *lower_bound(l, l + len, a[i]) = a[i];
    }
    return len;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        scanf(" %d", &a[i]);
    cout << lis();
}

注：本题还可以用树状数组求解