AcWing 896. 最长上升子序列 II

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 896. 最长上升子序列 II 原题链接简单

作者：

phac123 , 2019-07-17 14:26:23 , 所有人可见 , 阅读 22846

158

70

题目描述

最长上升子序列 II

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

输入格式
第一行包含整数N。

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

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

数据范围
1≤N≤100000，
−109≤数列中的数≤109

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

算法1

思路：首先数组a中存输入的数（原本的数），开辟一个数组f用来存结果，最终数组f的长度就是最终的答案；假如数组f现在存了数，当到了数组a的第i个位置时，首先判断a[i] > f[cnt] ？若是大于则直接将这个数添加到数组f中，即f[++cnt] = a[i];这个操作时显然的。
当a[i] <= f[cnt] 的时,我们就用a[i]去替代数组f中的第一个大于等于a[i]的数，因为在整个过程中我们维护的数组f 是一个递增的数组，所以我们可以用二分查找在 logn 的时间复杂的的情况下直接找到对应的位置，然后替换，即f[l] = a[i]。

我们用a[i]去替代f[i]的含义是：以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个。

这样当我们遍历完整个数组a后就可以得到最终的结果。

时间复杂度分析：$O(nlog n)$

C++ 代码

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

const int maxn = 1e5 + 5;

int a[maxn], f[maxn];
int cnt;

inline int find(int x) {
    int l = 1, r = cnt; 
    while(l < r) {
        int mid = l + r >> 1;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

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

    f[++cnt] = a[1];
    for(int i = 2; i <= n; i ++) 
        if(a[i] > f[cnt]) f[ ++ cnt] = a[i];
        else {
            int tmp = find(a[i]);
            f[tmp] = a[i]; 
        }

    printf("%d\n", cnt);

    return 0;
}

53 评论

zaiwind 2022-03-25 18:04

比y总牛逼

图灵酱 11个月前

确实

正态 10个月前

lower_bound()写法

#include<bits/stdc++.h>

#define rep(i, a, b) for(int i = a; i < b; i++)

using namespace std;

const int N = 1e5 + 10;
int a[N], f[N]; //f数组存储我们的性质最好的最长上升子序列


int main()
{
    int n; 
    cin >> n;
    rep(i, 1, n + 1) cin >> a[i];

    f[1] = a[1];
    int idx = 1;
    rep(i, 2, n + 1) //开始遍历其余数组元素
    {
        int x = a[i];
        if(x > f[idx]) //严格单调递增
        {
            f[++idx] = x;    
        }else //二分查找替换位置
        {
            //lower_bound为什么设置左闭右开呢，就是为了让你在第二个参数直接加上数组长度就ok了～
            int pos = lower_bound(f + 1, f + 1 + idx, x) - f; //lower_bound代替二分～
            f[pos] = x;
        }
    }

    cout << idx << endl; //最长上升子序列的长度

    return 0;
}

算法小菜鸟 2023-07-08 20:39

哦哦！懂了！当a[i] <= f[cnt] 的时,我们就用a[i]去替代数组f中的第一个大于等于a[i]的数。这里是找的第一个大于等于a[i]的数，然后把它替换成a[i]。y总找的是最大的小于a[i]的数，所以y总的代码是 q[r + 1] = a[i] ，即把找到的数的后面那个数替换成a[i],两者是等价的

算法小菜鸟 2023-07-08 21:01

然后这里为什么循环结束后直接输出f数组的长度就是答案，是因为f数组（也就是y总说的q数组）存的是每种长度的最长上升子序列的结尾的最小值。详细解释参考第一篇题解中天蓝色鸽子的评论（点赞最多的那位大佬）

梓川枫 8个月前

哥们，这么写虽然cnt的值是对的，但是最长子序列不对
比如10
46 -21 33 9 20 35 -41 43 -46 0 这组数据，最长上升子序列长度为5，按照题目的题意应该是-21，9，20，35，43
但是用您的这个代码逻辑输出的结果就是-46 0 20 35 43

梓川枫 8个月前

-46，0不应该跑到20，35，43的前面

种花家的兔兔 7个月前回复了梓川枫的评论

但是f数组存的本来就不是最长子序列啊

种花家的兔兔 7个月前回复了种花家的兔兔的评论

f[i]表示的是长度为i的上升子序列的结尾最小是多少

ZhiJieLuanDa 4个月前

“我们用a[i]去替代f[i]的含义是：以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个。”

lmsyhs 2022-02-20 22:46

有一个疑惑就是这样的话打印出来的子序列这样它会变 , 当然子序列的长度是没有问题的 , 算是一个缺陷了

fanbo 2022-06-01 22:45

确实是这样的，1 2 4 6 3 7，输出的话是 1 2 3 6 7

糖豆 2022-07-08 10:02

可以配合一个pos数组，就能解决正确LIS输出了：

#include <bits/stdc++.h>
using namespace std;

/*
测试用例：
8
-7 10  9  2  3  8  8  1
*/

const int N = 1e5 + 10;
int n, a[N];
int f[N], idx; // dp数组，idx:下标指针,因为从1开始，也可以理解为个数、LIS的最大长度
int pos[N];    // p数组，记录原始数组每个数字在dp数组中出现的位置,也就是这个数字a[i]它当过第几名

//输出一条LIS路径,判断需要配合Special Judge
void print() {
    vector<int> path;
    for (int i = n; i >= 1 && idx; i--) //找够idx个就结束了
        if (pos[i] == idx) {            //找到idx,idx-1,idx-2,...的名次
            path.push_back(a[i]);       //记录idx,idx-1,idx-2,...名次的数字入路径数组
            idx--;
        }
    for (int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
}

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

    // 1、出发
    f[++idx] = a[1];
    pos[1] = 1; //每个数字都会产生一个在f数组中的位置记录

    // 2、后续元素进行处理
    for (int i = 2; i <= n; i++)
        if (a[i] > f[idx]) {
            f[++idx] = a[i];
            pos[i] = idx; //每个数字都会产生一个在f数组中的位置记录
        } else {
            int t = lower_bound(f + 1, f + idx + 1, a[i]) - f;
            f[t] = a[i];
            pos[i] = t; //每个数字都会产生一个在f数组中的位置记录
        }
    //输出lis长度
    printf("%d\n", idx);

    //输出LIS路径方法
    print();

    return 0;
}