题目:
设有一个正整数的序列:d1,d2,…,dn,对于下标i1<i2<…<im,若有di1≤di2≤…≤dim
则称存在一个长度为m的上升序列。
例如,下列数列
13 7 9 16 38 24 37 18 44 19 21 22 63 15
对于下标i1=1,i2=4,i3=5,i4=9,i5=13,满足13<16<38<44<63,则存在长度为5的上升序列。
#include<stdio.h>
#define MAX 10000
void vInput(int nDa[],int nN);
int nGetSum(int nDa[],int nN);
void vOutput(int nRet);
int main()
{
int nNum;
int nAns;
int nData[MAX];
while(1 == scanf("%d",&nNum))
{
vInput(nData,nNum);
nAns = nGetSum(nData,nNum);
vOutput(nAns);
}
return 0;
}
void vInput(int nDa[],int nN)
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nDa[i]);
}
}
int nGetSum(int nDa[],int nN)
{
int i,j;
int nTemp;
int nCount[MAX];
int nOut = 1;
//初始化一维数组,存放最后一位值到当前值最长上升子序列的个数
for(i=1;i<=nN;i++)
{
nCount[i] = 0;
}
//以自底向上的方法,从后往前
for(i=nN;i>=1;i--)
{
nTemp = 0;
//当前值往后遍历,找到上升子序列的个数最大的
for(j=i+1;j<=nN;j++)
{
if(nDa[i] < nDa[j])
{
if(nTemp < nCount[j])
nTemp = nCount[j];
}
}
nCount[i] = nTemp+1;
if(nOut <= nTemp)
nOut = nTemp+1;
}
return nOut;
}
void vOutput(int nRet)
{
printf("%d\n",nRet);
}
/*
7
1 5 9 6 5 8 9
*/
分享到:
相关推荐
javascript javascript_leetcode面试题解动态规划问题之第300题最长上升子序列_题解
提供了求出最长上升子序列中各个元素的个数以及打印出各个元素的方法,希望能对大家有所帮助。
动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP
你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 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 提示 一,对输入字符串的处理 注意:这道题和其他题的输入输出不同,这题...
动态规划的经典题目最长上升子序列,而且是经过二分优化的NlogN复杂度算法
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
8596 最长上升子序列(必做) 时间限制:300MS 内存限制:1000K 提交次数:255 通过次数:118 题型: 编程题 语言: G++;GCC;VC Description A numeric sequence of ai is ordered if a1 Let the subsequence of the ...
输入序列,求最长上升子序列的长度,算法复杂度nlgn
动态规划解决LIS问题的一种常见方法是使用一个数组来记录以每个元素结尾的最长上升子序列的长度。假设我们有一个数组 `nums`,其中 `dp[i]` 表示以 `nums[i]` 结尾的最长上升子序列的长度。那么我们可以按照以下步骤...
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的不下降序列。程序...
这是一个一个关于如何求解最长公共上升子序列(LCIS)的平方算法,里面写的十分的详细,所以就和大家分享了,希望大家喜欢。
300. 最长上升子序列 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子...
最长上升子序列
最长上升子序列通过本文的介绍,相信你对最长上升子序列问题有了更为深入的了解。无论是从理论角度还是实践角度,最长上升子序列都是一个值得深入研究和探索的问题。希望本文能为你提供有益的参考和启发,助你在算法...
动态规划经典问题算法:合唱队行,最大k乘积,0-1背包问题,最长上升子序列,田忌赛马,花瓶插花
序列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。
此资源有助于帮助初学者较快掌握nlogn算法求动态规划中的经典例题---最长不上升序列(n>100000)
给定一个无序的整数数组,找到其中最长上升子序列的长度。 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:可能会有多种最长上升子序列的组合,你只需要输出...