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

895. 最长上升子序列

时间:2022-09-28 00:00:33浏览次数:53  
标签:上升 895 int 序列 include 最长

最基础的最长上升子序列问题
这里用的是dp做法
定义f[i]为从1~i的所有上升子序列最大的长度
双重循环,以a[i]为最后一个数,枚举所有小于a[i]的数a[j]作为倒数第二个数,对于所有情况,最长子序列的长度即为f[i]=f[j]+1(f[j]为所有合法情况下的最大值)

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int f[N], a[N];
int n,ans;
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 j = 1; j < i; j++)
		{
			if(a[j] <  a[i])
				f[i]=max(f[i],f[j]+1);
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,f[i]);
	cout << ans << endl;
	return 0;
}

 

标签:上升,895,int,序列,include,最长
From: https://www.cnblogs.com/lxl-233/p/16736498.html

相关文章

  • 序列化之Serializer
    常用字段类和字段参数1.CharFieldBooleanFieldIntegerFieldDecimalField2.返回格式ListField:{hobby:['篮球','足球']}DictField:{wife:{'name':'barry'}}......
  • drf之模型类序列化器ModelSerialize
    序列化常用字段charFieldBooleanFieldIntegerFieldDecimaField#ListField:{name:'summer',hobby:[1,2,3,4]}#DictField:{nane:'summer',wife:{'name':'哈哈哈'}}......
  • Serializer序列化与ModelSerializer序列化
    Serializer序列化与ModelSerializer序列化序列化类高级用法之cource,修改序列化字段名字用法一使用cource的时候,字段参数可以指定序列化哪个参数,如果指定别人的字段那......
  • drf序列化类
    目录序列化类常用字段类和字段参数1.常用字段2.常用字段参数2.1.给CharField字段类使用的参数2.2.给IntegerField字段类使用的参数2.3.通用参数2.4.重点序列化类高级用法之......
  • 序列化类常用字段类和字段参数、序列化类高级用法之source、序列化类高级用法之定制序
    目录序列化类常用字段和字段参数常用字段类需要记住的字段类常用字段参数序列化类高级用法之source,修改序列化字段名字序列化类高级用法之定制序列化字段的俩种方式方式一......
  • drf ModelSerializer模型类序列化器
    序列化类的常用字段类和字段类参数 序列化类的常用字段类和字段类参数序列化类的字段类字段名=serializers.字段类型(字段参数)主要的字段类CharFieldBoolean......
  • 今日内容 序列化类的高级用法
    序列化类常用字段类和字段参数常用字段类型:字段字段构造方式BooleanFieldBooleanField()NullBooleanFieldNullBooleanField()CharFieldCharField(......
  • 【Django-rest-framework框架】第03回 序列化类字段与高级用法
    目录1.序列化类常用字段与字段参数1.1常用字段类型1.2选项参数1.3通用参数2.序列化类高级用法之sourse2.1source可以指定序列化表中得哪个字段2.2source如果是方......
  • drf之序列化类
     一、序列化类的常见字段类和常见参数1.1常见的字段类字段字段构造方式BooleanFieldBooleanField()NullBooleanFieldNullBooleanField()CharFieldChar......
  • 做题记录整理dp13 P7914 [CSP-S 2021] 括号序列(2022/9/26)
    P7914[CSP-S2021]括号序列非常考思维的思维题(甚至做到了让全广西都恐惧(似乎广西连拿暴力分的人都没有))由于看了题解,所以这题相当于是在巨人的肩膀上做题了。。。而且......