首页 > 其他分享 >最长上升子序列

最长上升子序列

时间:2024-08-07 15:17:42浏览次数:13  
标签:5010 include const int len find 序列 上升 最长

普通
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N = 5010;
int n, f[N];
int a[N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];

	for (int i = 1; i <= n; i++)f[i] = 1;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
	if(a[i]>a[j])f[i] = max(f[i], f[j] + 1);

	int res = 0;
	for (int i = 1; i <= n; i++)
		res = max(res, f[i]);

	cout << res;
}
二分优化
#include<iostream>

using namespace std;
const int N = 5010;
int a[N], b[N], f[N];
int n;
int len;
int find(int x) {
	int l = 1, r = len, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (b[mid] == x)return mid;
		else if (x < b[mid])r = mid - 1;
		else l = mid + 1;
	}
	return l;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	int i, j;
	len = 1; b[1] = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] > b[len])
			b[++len] = a[i];
		else
		{
			j = find(a[i]);
			b[j] = a[i];
		}
	}
	cout << len << endl;
}

标签:5010,include,const,int,len,find,序列,上升,最长
From: https://www.cnblogs.com/windzhao6/p/18347098

相关文章

  • 《双序列拓展》
    描述称某个序列B={b1​,b2​,⋯,bn​}是另一个序列A={a1​,a2​,⋯,am​}的拓展当且仅当存在正整数序列L={l1​,l2​,⋯,lm​},将ai​替换为li​个ai​后得到序列B。例如,{1,3,3,3,2,2,2}是{1,3,3,2}的拓展,取L={1,1,2,3}或{1,2,1,3};而{1,3,3,2}不是{1,3,......
  • 基于Prophet时间序列模型预测股票价格趋势
    作者:老余捞鱼原创不易,转载请标明出处及原作者。写在前面的话:     在当今复杂多变的金融市场中,股票价格预测一直是投资者和分析师关注的焦点。本文旨在利用Prophet时间序列模型对股票价格趋势进行预测。Prophet模型是一种基于可分解的时间序列模型,由趋势项、季节......
  • PLEK升级了:PLEKv2工具在RNA序列分析中的卓越表现
    摘要:使用PLEKv2识别鉴定lncRNA,只需要输入RNA的序列(fa文件)即可。 在生物信息学领域,长非编码RNA(lncRNA)和信使RNA(mRNA)的准确区分对于理解基因调控机制至关重要。随着深度学习技术的兴起,我们迎来了PLEKv2——PLEK工具的全新升级版,它在RNA序列分类精度方面取得了显著提高。这里探......
  • 使用 Python 中的 Matplotlib 和时间序列索引生成奇怪的图
    我正在尝试使用Python中的Matplotlib绘制一些时间序列数据,但生成的图看起来很奇怪,我不明白为什么。这是我正在使用的代码:filtered_df=df.loc[(df.index>'2010-01-01')&(df.index<='2010-01-08')]#Plottingthedatafig,axs=plt.subplots(1,1,figsize=(12,......
  • 代码随想录 day 47 回文子串 | 最长回文子序列
    回文子串回文子串解题思路dp数组的状态是判断以i结尾,j开始的字符串是否为回文,用bool类型存储,之后当i和j的字符串相等时,通过计算它们之间的距离和判断它们之间是否为回文串来进行递归。知识点回文,动态规划心得如果不看题解根本想不到怎么做最长回文子序列最长回文子序列......
  • QRGRU-基于分位数回归门控循环单元的时间序列/回归区间概率预测matlab代码
    本人整理了QRGRU基于分位数回归门控循环单元的时间序列/回归区间概率预测matlab代码,该代码质量优异,出图精美,有详细注释,适合新手学习使用。1.多变量回归或时序预测均可,不加价~适用于matlab2020及以上。可任意选择置信区间,评价指标包括R2、MAE、区间覆盖率picp、区间平均宽度百分......
  • 无法反序列化解码 JWT python 时的关键数据
    我正在使用pyjwt库来解码JWT令牌。我在解码时遇到此错误。代码在文档中给出。importjwtencoded_jwt='''eyJ0eXAiOiJKV1QiLCJhbG......'''secret=b''''-----BEGINPUBLICKEY-----MIIFRjCCBC6gAwIBAgIQCIdSGhpikQCjOIY154XoqzANBgkqhkiG9......
  • 对象序列化和反向序列化
    对象序列化和反向序列化目录对象序列化和反向序列化对象序列化:对象反向序列化:注意事项:在Java中,对象序列化是指将对象的状态信息转换为可以存储或传输的形式的过程。序列化的对象可以被写入到文件、数据库或通过网络传输。反向序列化,也称为反序列化,是序列化过程的逆过程,即将序列......
  • 对象序列化与反序列化
    对象序列化与反序列化在Java中,对象序列化是指将对象的状态信息转换为可以存储或传输的形式的过程。反序列化则是将这些信息恢复为对象的过程。Java通过实现java.io.Serializable接口来支持对象的序列化和反序列化。以下是对象序列化和反序列化的基本概念和步骤:1.使类实现S......
  • Datawhale AI 夏令营 市场博弈和价格预测 时间序列挖掘
    前言在上一篇,已经通过探索性数据分析(EDA)深入理解赛题“市场博弈和价格预测”得到了以下启发,此篇就可以完成一个时间序列挖掘任务进行上分!导包&读取数据请将数据文件electricity_price_parsed放在代码文件同级的data文件夹路径下载链接:https://linklearner.com/acti......