求数组的最长递减子序列

发表于 | 分类于 | 阅读次数:

给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。

输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。

输出为一行，最长递减子序列的结果，数字间用空格分隔（测试case中只会有一个最长递减子序列）。

样例1

输入：

8
9 4 3 2 5 4 3 2

输出：

9 5 4 3 2

思路：求最长递减序列，我的做法是把输入数据反向，然后求用我会做的求最长递增序列，当然我用的求法不是O（n^2）的，那样我觉得会超时，所以我用的O（nlogn）的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int g[30010],num[30010],d[30010];
int main(){
    int n;
    scanf("%d",&n);
    int inf=0x7fffffff;
    fill(g,g+n,inf);
    for(int i=0;i<n;++i){
        scanf("%d",&num[n-1-i]);
    }
    //核心代码begin
    for(int i=0;i<n;++i){
        int j=lower_bound(g,g+n,num[i])-g;
        g[j]=num[i];
        d[i]=j+1;
    }
    //end
    int s=*max_element(d,d+n);
    for(int i=n-1;i>=0;--i)
    {
        if(s==d[i])
        {
            if(s!=1)
                printf("%d ",num[i]);
            else
                printf("%d\n",num[i]);
            --s;
        }
    }
    return 0;
}

打个小广告

欢迎加入我的小专栏「基你太美」一起学习。