问题描述
一个数的序列 bi,当 b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一
个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里 1 <= i1 < i2 < ... <
iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。
这些子序列中最长的长度是 4,比如子序列(1, 3, 5, 8).
你的任务,就是对于给定的序列,求出最长上升子序列的长度。
输入数据
输入的第一行是序列的长度 N (1 <= N <= 1000)。第二行给出序列中的 N个整数,这些
整数的取值范围都在 0到 10000。
输出要求
最长上升子序列的长度。
输入样例
7
1 7 3 5 9 4 8
输出样例
4
#include <stdio.h>
#include <string.h>
int arry[1001];
int len[1001];
int main()
{
int i, j;
int n, maxLen;
scanf("%d", &n);
for( i = 1; i <= n; i++ )
{
scanf("%d", &arry[i]);
}
len[1] = 1;
for( i = 2; i <= n; i++ )
{
maxLen = 0;
for( j = 1; j < i; j++ )
{
if( len[j] > maxLen && arry[j] < arry[i] )
{
/*
*如果i位置的权值大于j位置的权值,
*且j处得长度大于j以前的长度,i才能加入到j的后面
*/
maxLen = len[j];
}
}
len[i] = maxLen+1;
}
maxLen = 0;
for( i = 1; i <= n; i++ )
{
if( len[i] > maxLen ) maxLen = len[i];
}
printf("%d\n", maxLen);
return 0;
}
分享到:
相关推荐
提供了求出最长上升子序列中各个元素的个数以及打印出各个元素的方法,希望能对大家有所帮助。
最长上升子序列,好不容易得到的资源,可以说是非常非常有用
输入序列,求最长上升子序列的长度,算法复杂度nlgn
你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入字符串的处理 注意:这道题和其他题的输入输出不同,这题...
1259:【例9.3】求最长不下降序列 【题目描述】 设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j),若存在i1…且有b(i1)(i2)<…(ie)则称为长度为e的不下降序列。程序...
An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 ...
给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只需要...
给定一个无序的整数数组,找到其中最长上升子序列的长度。 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:可能会有多种最长上升子序列的组合,你只需要输出...
如 [10, 9, 2, 5, 3, 7, 101, 18],其最长上升子序列的长度为4。最长上升子序列为 [2,5,7,101]注意1:什么是子序列?方法1/
题面优化方法优化解法归类为贪心(每一步都是当前情况下的最优解,得到的就是最优解)把所有长度不同的递增最长子序列 的 结尾的最小值存到一个数组(q[])里面去,那
给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只需要...
给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只需要...
1008的第一问和1009一样,第二问需要用到Dilworth分割定理:要求出最长不上升子序列的最少划分数,只需要求出这个序列中最长上升子序列的长度,这就转化成了和1009完全类似的问题。 1009 本质是找出序列中的一个最长...
O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸多边形面积 半平面交 计算几何库 数据结构 闭散列法整数hash 开散列法整数hash 字符串hash 堆 二维树状数组 ...
最长上升子序列 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 dp[i] 的值代表以nums[i]结尾的最大递增子序列的长度。 [10,9,2,5,3,7,101,18] dp[5]:以nums[5],也...
问题描述 东东有两个序列A和B。...这个题是基本的动态规划问题,LIS是最长上升子序列,LCS是最长公共子序列。 求解LIS就是设dp[i]为以当前元素结尾的最长上升序列,那么dp[i]=max(dp[j]∣j<i&&a
5.4.3 用T-SQL解决最长上升子序列的长度问题 5.5 总结 第6章 子查询、表表达式和排名函数 6.1 子查询 6.1.1 独立子查询 6.1.2 相关子查询 6.1.3 行为不当的子查询 6.1.4 不常用的谓词 6.2 表表达式(Table ...
5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5 总结229 第6章 子查询、表表达式和排名函数231 6.1 子查询232 6.1.1 独立子查询232 6.1.2 相关子查询235 6.1.3 行为不当的子查询244 6.1.4 不常用的谓词245 6.2 ...
5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5 总结229 第6章 子查询、表表达式和排名函数231 6.1 子查询232 6.1.1 独立子查询232 6.1.2 相关子查询235 6.1.3 行为不当的子查询244 6.1.4 不常用的谓词...