计蒜客求数组的最长递减子序列（nlogn+路径打印）

小鱼儿 2024-02-18 16:32 20阅读 0赞

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

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

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

##### 样例输入 #####

8
    9 4 3 2 5 4 3 2

##### 样例输出 #####

9 5 4 3 2

思路：

我们知道nlogn算法中有一个B\[len\]数组，表示长度为len的子序列对应的最大（这里要求递减嘛）末尾（比如说子序列10,9,5和10,9,7, 此时最小末尾是B\[3\]=7，最长递减序列嘛，肯定是当长度相同时，末尾数越大越好）。

路径的记录：用num\[i\]来储存长度（最大末尾为d\[i\]的长度），关键来了，当LIS过了一遍之后，从后向前遍历（为什么呢？这是因为在执行nlogn的时候，同一长度len对应了多个最大末尾（因为i->n的过程中最大末尾不断更新：不同的i对应，但都被num\[i\]记录下来了））；很有意思的一道题，值得细嚼慢咽，比较靠思维。

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int INF = 1e9;
    const int maxn = 1e3+10;
    int p[maxn],a[maxn];
    int num[maxn];  //记录长度为i的最长递减子序列的len 
    int B[maxn]; //最大末尾的位置 
    
    int search(int x,int y,int tmp){
    	while(x < y){
    		int mid = x + (y-x)/2;
    		if(tmp>=B[mid]) y = mid;
    		else x = mid+1;
    	}
    	return x;
    }
    
    int main(){
    	int N;
    	while(scanf("%d",&N)==1){
    		for(int i = 1; i <= N; i++)
    		  scanf("%d",&a[i]);
    		  
            int len =1;
            B[len] = a[1];
            num[1] = 1;
            for(int i = 2; i <= N; i++){
            	if(a[i] < B[len]){
            		B[++len] = a[i];
            		num[i] = len;
    			}else {
    				int j = search(1,len,a[i]);
    				B[j] = a[i];
    				num[i] = j;
    			}
    		}
    		
    		int last = -INF , l = len;
    		for(int i = N; i >= 1; i--){
    			if(!l) break;
    			if(l == num[i] && a[i] > last){
    				last = a[i];
    				p[l--] = a[i];
    			}
    		}
    		
    		printf("%d",p[1]);
    		for(int i = 2; i <= len; i++)
    		printf(" %d",p[i]);
    		printf("\n");
    	}
    	return 0;
    }