流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

最长不下降子序列（LIS）

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-19 01:22:04 浏览：332　|　评论：0　

PS:只做简单总结，想深入了解原理请移步 搜索其它文章

------------

问题：
```
在一个数字序列A中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

```
一般有两问：
1.问最长子序列长度
2.输出最长子序列
```
时间复杂度：O(n^2)

dp[i] 为 前i个元素以第i个结尾的最长非递减子序列
 ```

代码1：
```
#include<iostream>
#include<algorithm>
using namespace std;
//百炼OJ 2757 
int main(){
	int n,*p,*maxlen;
	while(cin>>n) {
		p=new int[n];
		maxlen=new int[n];
		for(int i=0;i<n;i++){
			cin>>p[i];
			maxlen[i]=1;
		}
		for(int i=1;i<n;i++)
		//每次求以第i个数为终点的最长上升子序列 长度 
			for(int j=0;j<i;j++)
			//查看以第j个数为终点的最长上升子序列 
				if(p[i]>p[j]) 
				maxlen[i]=max(maxlen[i],maxlen[j]+1);
		cout<<*max_element(maxlen,maxlen+n)<<endl;
		delete [] p;
		delete [] maxlen;
		//时间复杂度O(n^2) 
	}
	 	
	return 0;
} 
```

------------

优化解法：
```
时间复杂度：O(nlog(n))
```
参考文章：
[最长不下降子序列 NlogN && 输出序列](https://www.cnblogs.com/milky-w/p/8431333.html "最长不下降子序列 NlogN && 输出序列")

根据上面文章总结实现思路：
```
（  a[]用作接收输入序列  序列长度为n  ）
1.新开一个数组d[]，用它来记录每个序列的末尾元素，
（len 表示当前凑出的最长序列长度，也就是当前 d 中的最后那个位置）
2.枚举a[i] 与 d[len]比较，
	如果a[i]>=d[len],则d[len+1]=d[i]
	否则 a[i]在d[]的前 len-1 项中，找出第一个大于d[k]的数的下标
(1<=k<=len-1) {优化点：d[]序列具有单调性，可用二分}
核心代码： int j = upper_bound(d + 1, d + len + 1, a[i]) - d;
```
知识点补充：
[ upper_bound和lower_bound用法](https://blog.csdn.net/u011008379/article/details/50725670 " upper_bound和lower_bound用法")

代码经过改编优化
 ```
//From - Milky Way
#include <cstdio>
#include <algorithm>
using namespace std;
int d[1005],a[1005], len = 1;
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
    }
    d[1] = a[1];
    for (int i = 2; i <= n; ++ i) {
        if (d[len] <= a[i]) {
            d[++ len] = a[i];
        } else {
            int j = upper_bound(d + 1, d + len + 1, a[i]) - d;
            d[j] = a[i];
        }
    }
 	for(int i=1;i<=len;i++)
 		printf("%d ",d[i]);
 	printf("\n%d\n",len);
 
    return 0;
}

//最长不下降之输出子序列 - NlogN
//https://blog.csdn.net/hi_baymax/article/details/82151228
 ```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-亲密数（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

最长不下降子序列（LIS）

评论区

精彩推荐

人民币问题（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

数字游戏（C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

数列问题（C语言代码）

1231题解(注意理解“输入多个测试实例”)

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

求圆的面积（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C++代码）

C二级辅导-进制转换 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言训练-亲密数 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

最长不下降子序列（LIS）

评论区

精彩推荐

人民币问题 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

数字游戏 （C++代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

数列问题 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

求圆的面积 （C语言代码）

C二级辅导-进制转换（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-亲密数（C++代码）

　　评论区

人民币问题（C语言代码）

数字游戏（C++代码）

数列问题（C语言代码）

求圆的面积（C语言代码）