怎样做网站和网站的友情链接,官网优化 报价,百度电商广告代运营,公司网站模板 网盘下载1. 题目
题目链接#xff1a;
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 输入样例#xff1a;
6
1 2 4 1 3 4
输出样例#xff1a;
4
说明/提示#xff1a;
分别取出 1、2、3、4 即可。
2. 具体实现
2.1 一般做法 dp[i]表示第i个位置的…1. 题目
题目链接
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 输入样例
6
1 2 4 1 3 4
输出样例
4
说明/提示
分别取出 1、2、3、4 即可。
2. 具体实现
2.1 一般做法 dp[i]表示第i个位置的最长上升子序列个数
//思路
//dp[i]表示第i个位置的最长子序列个数
//dp[i]也就是找到前面1到i-1位置上值小于a[i]的最大dp值
#includebits/stdc.h
using namespace std;
const int N1e610;
int a[N],dp[N];
int main(void){int n;cinn;for(int i1;in;i){cina[i];dp[i]1;}int res1;for(int i2;in;i){int tmax0;for(int j1;ji;j){ //遍历前i-1项找到值a[i]的最大dp值 if(a[i]a[j]) tmaxtmaxdp[j]?tmax:dp[j];}dp[i]tmax1;resmax(res,dp[i]);}coutres; return 0;
}
时间复杂度: O(n^2)空间复杂度: O(N) 2.2 优化
dp[i]表示最长子序列长度为i的最小尾数
//思路2
//dp[i]表示最长上升子序列长度为i的最小尾数
//显而易见dp是一个递增序列
//我们对每一个数进行遍历
//每一次找到值大于a的位置进行更新即可。
#includebits/stdc.h
using namespace std;
const int N1e610; //最小尾数最大页只能为1e6
int dp[N];
int a[5010];
int main(void){int n;cinn;for(int i1;in;i){cina[i];}dp[1]a[1]; //初始化 int ans1;for(int i1;in;i){//找到dp中值第一个大于a[i]的位置int tlower_bound(dp1,dp1ans,a[i])-dp; dp[t]a[i];ansmax(ans,t);}coutans; return 0;
}
时间复杂度: O(nlogn)空间复杂度: O(n) lower_bound()函数是C提供的二分查找的函数具体使用方法可以看以下文章 关于lower_bound( )和upper_bound( )的常见用法_lowerbound和upperbound-CSDN博客 代码自己写的有什么问题欢迎指正。
都看到这里了点个赞再走吧(*^_^*)
