最长上升子序列O(nlogn)

秒速五厘米 2022-08-17 14:23 141阅读 0赞

模板：

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    const int MAXN=500010;
    int a[MAXN],b[MAXN];//a数组为原数组，b数组为存放最长上升子序列的数组
    
    int search(int num,int low,int high) //利用二分查找的方法找到一个位置，把num插入
    {
        int mid;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(num>=b[mid]) low=mid+1;
            else high=mid-1;
        }
        return low;
    }
    int DP(int n)
    {
        int i,len,pos;
        b[1]=a[1];
        len=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>=b[len])//若a[i]比b[]数组中的最大的还要大，则将其直接插入末尾
            {
                len=len+1;
                b[len]=a[i];
            }
            else
            {
                pos=search(a[i],1,len);//关键：用二分的方法在b[]数组中找到第一个比a[i]大的位置并且让a[i]代替这个位置
                b[pos]=a[i];
            }
        }
        return len;
    }
    int main()
    {
        int n;
        int lenb;
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            lenb=DP(n);
            printf("最长上升子序列长度为： %d\n",lenb);
            for(int i=1;i<=lenb;i++)
            {
                printf("%d ",b[i]);
            }
            printf("\n");
        }
        return 0;
    }

![这里写图片描述][20151126203726434]  
2015-11-26 21:00

[20151126203726434]: /images/20220731/f8847fc2b66141a8bdb27964c8b80452.png

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关最长上升子序列模型 AcWing 272. 最长公共上升子序列

最长上升子序列模型 AcWing 272. 最长公共上升子序列原题链接 [AcWing 272. 最长公共上升子序列][AcWing 272.] 算法标签

缺乏、安全感/ 2023年09月28日 14:26/ 0 赞/ 42 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 250 阅读

相关最长上升子序列

问题描述一个数的序列ai，当a1< a2< ... < aS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些

深藏阁楼爱情的钟/ 2022年08月18日 00:40/ 0 赞/ 251 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,

川长思鸟来/ 2022年07月13日 01:55/ 0 赞/ 219 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 249 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 275 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 337 阅读

相关最长上升子序列

最长上升子序列 Time Limit: 3000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Probl

傷城~/ 2022年05月30日 10:09/ 0 赞/ 238 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)

一时失言乱红尘/ 2022年05月16日 01:28/ 0 赞/ 275 阅读

相关最长上升子序列，最长不下降子序列

最长上升子序列 include<iostream> include<cstdio> using namespace std; const in

深藏阁楼爱情的钟/ 2022年05月13日 22:55/ 0 赞/ 304 阅读