8596 最长上升子序列(必做)
时间限制:300MS 内存限制:1000K
提交次数:255 通过次数:118
题型: 编程题 语言: C++;C;VC;JAVA
Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
输入格式
There are several test cases. Every test case includes two lines. The first line contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000 When N is 0, it indicates test to end.
输出格式
Output must contain a single integer for every test case ---- the length of the longest ordered subsequence of the given sequence.
输入样例
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
#include <iostream>
#include <stdio.h>
using namespace std;
int n;
int a[10000]; //The second line contains the elements of sequence - N integers in the range from 0 to 10000 each,
int f[10000]; // 注意数组大小
int max1=0;
int num=0;
void searchM()
{
for(int i=0;i<n;i++)
{
f[0] = 1; max1 = 0; //初始化
for(int j=0;j<i;j++) // 从0到i的前一位
{
if(a[i]>a[j]) // 如果比当前位小
{
if(max1 < f[j]) // 更新 记录最大长度 注意是J
max1 = f[j];
}
}
f[i] = max1+1; //把从第一位到当前位的最大长度+1 (加上自身)
}
}
int main()
{
//freopen("in.txt","r",stdin);
cin >>n;
while(n)
{
for(int i=0;i<n;i++)
cin >>a[i];
searchM() ;
int temp=f[0];
for(int i=1;i<n;i++)
{
if(f[i]>temp)
temp=f[i];
}
cout<< temp<<endl;
cin >>n;
}
return 0;
}
相关推荐
提供了求出最长上升子序列中各个元素的个数以及打印出各个元素的方法,希望能对大家有所帮助。
你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 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 提示 一,对输入字符串的处理 注意:这道题和其他题的输入输出不同,这题...
输入序列,求最长上升子序列的长度,算法复杂度nlgn
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP
最长上升子序列 最长上升子序列(Longest Increasing Subsequence,简称LIS)是指在一个序列中找到一个最长的子序列,使得子序列中的元素是递增排列的。这个问题在计算机科学中很常见,有多种解决方法,其中动态...
动态规划的经典题目最长上升子序列,而且是经过二分优化的NlogN复杂度算法
53、1281:最长上升子序列(A)+书画相关链接(十七)-2020.01.19 53、1281:最长上升子序列(A)+书画相关链接(十七)-2020.01.19
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的不下降序列。程序...
300. 最长上升子序列 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子...
这是一个一个关于如何求解最长公共上升子序列(LCIS)的平方算法,里面写的十分的详细,所以就和大家分享了,希望大家喜欢。
最长上升子序列通过本文的介绍,相信你对最长上升子序列问题有了更为深入的了解。无论是从理论角度还是实践角度,最长上升子序列都是一个值得深入研究和探索的问题。希望本文能为你提供有益的参考和启发,助你在算法...
最长上升子序列
最长上升子序列 编辑距离问题、货物堆积问题、骑士周游问题、数组分割问题、资源分配问题、最长上升子序列问题
序列Z=,C,D,B>是序列X=,B,C,B,D,A,B>的子序列,相应的递增下标序列为,3,5,7>。 一般地,给定一个序列X=,x2,…,xm>,则另一个序列Z=,z2,…,zk>... 你的任务是:给定2个序列X、Y,求X和Y的最长公共子序列Z。
给定一个无序的整数数组,找到其中最长上升子序列的长度。 输入: [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/