求数组的最长递减子序列

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

输入包括两行,第一行包括一个正整数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;
}

打个小广告

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