题目描述

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

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

样例

7
3 1 2 1 8 5 6

最长上升子序列为1,2,5,6,长度为4

算法1

动态规划

时间复杂度

$O(n^2)$

比较直观，这里就不多赘述

C++ 代码

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

const int N = 1010;
int n;
int a[N], f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < n; j++) 
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}

算法2

在这道问题中，数据开到了1e5,显然$O(n^2)$的算法是不足以通过的，因此我们需要对上述算法进行优化。

在算法1中，时间的浪费在于第二层循环，有许多情况显然不是最优的，可以不进行下一步计算，我们优化就由此切入。

比如,在序列1 3 2中，序列1 3这种情况就是不需要重复计算的，因为显然序列1 2所可能形成的上升子序列长度一定是大于等于序列1 3。

由此，我们可以创建一个数组q，其中q[i]所存储的就是所有长度为i的上升子序列中，结尾元素的最小值。
对于每一个a[i],可以通过二分在数组q中查找第一个小于a[i]的元素，那么这个元素的下一个元素就一定大于等于a[i]，就可以用a[i]，来代替它，且每次替换后所得结果不会更少。q中元素的个数的最大值就是我们要求的答案

时间复杂度

$O(n \log(n))$

参考文献

算法基础课

C++ 代码

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

const int N = 100010;

int n;
int a[N], q[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    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 (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}