Skip to content

牛客网 NC26156 G. 最长递增长度#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: C/C++ 1秒，其他语言2秒

Memory Limit: C/C++ 32768K，其他语言65536K

1.2. Problem Description#

给定一个长度为 的整数序列 ，求这个序列中最长的严格递增子序列的长度。

1.3. Input#

第一行，一个整数，表示序列的长度

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

1.4. Output#

输出一个整数，表示最长递增子序列的长度

1.5. Sample Input#

6
4 0 5 8 7 8

1.6. Sample Output#

4

1.7. Note#

样例解释 子序列为 0 5 7 8

1.8. Source#

牛客网 NC26156 G. 最长递增长度

2. 解读#

题意：求最长递增子序列的长度。用 的 DP 试了一下超时了，所以这题可能需要使用 的算法。

题解：定义一个数组 d[] 存储最长递增子序列 ，len 统计d[]内数据的个数，list[] 存储原始序列。初始化 d[1] = list[1]，len = 1。根据下面的操作步骤进行操作。

  • 操作步骤：逐个处理 list[] 中的数字，例如处理到了 list[k]，进行判断
    • 如果list[k] 比d[] 末尾的数字更大，就加到 d[] 的后面。
    • 如果 list[k] 比 d[] 末尾的数字更小，就替换 d[] 中第 1 个大于它的数字。

以 list[] = {4, 8, 9, 5, 6, 7} 为例，具体的操作过程如下表所示。

i list[] d[] len 说明
1 4, 8, 9, 5, 6, 7 4 1 初始值 d[1] = list[1]
2 4, 8, 9, 5, 6, 7 4, 8 2 list[2] > d[1]，加到 d[]的后面
3 4, 8, 9, 5, 6, 7 4, 8, 9 3 d[] 后面加上 9
4 4, 8, 9, 5, 6, 7 4, 5, 9 3 5 比 d[] 末尾的 9 小，用 5 替换d[] 中第 1 个比 5 大的数字8
5 4, 8, 9, 5, 6, 7 4, 5, 6 3 用 6 替换 9
6 4, 8, 9, 5, 6, 7 4, 5, 6, 7 4 d[] 后面加上 7

3. 代码#

#include<iostream>
using namespace std;

const int NUM  = 5e4 + 1;
long long n, list[NUM];

int LIS()
{
    long long len = 1;
    long long d[NUM];
    // 初始化
    d[1] = list[1];
    // O(n)
    for (int i = 2; i <= n; i++) {
        // 符合递增的要求，加入
        if (list[i] > d[len]) {
            d[++len] = list[i];
        } else {
            // 替换，O(logn)
            long long j = lower_bound(d + 1, d + len + 1, list[i]) - d;
            d[j] = list[i];
        }
    }
    return len;
}

int main(){
    cin >> n;
    for(int i = 0; i< n;i++){
        cin >> list[i];
    }
    cout << LIS() << endl;
}

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top