题目:
设有一个正整数的序列: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
*/
分享到:
相关推荐
在算法领域,最长上升子序列(Longest Increasing Subsequence,LIS)问题是一个经典的问题,它在计算机科学中有着广泛的应用,例如在数据结构、排序算法以及动态规划等方面。本篇将详细介绍如何找出一个序列中长度...
本题解聚焦于LeetCode的第300题——最长上升子序列(Longest Increasing Subsequence, LIS),这是一个典型的动态规划问题。 动态规划是算法设计的一种策略,通过将复杂问题分解成更小的子问题来解决。在最长上升子...
最长上升子序列问题是一个经典的算法问题,通常在算法设计与分析、数据结构以及动态规划等领域中经常被提及。问题的核心是针对给定的序列,寻找一个最长的子序列,使得这个子序列中的任意两个元素按原有顺序比较都是...
动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP
本题通过动态规划的方法有效地解决了寻找最长上升子序列的问题。虽然时间复杂度为 \(O(n^2)\),但对于题目所给的数据范围(\(1 \leq N \leq 1000\))来说是足够高效的。此外,代码中还包含了输入输出的处理细节,...
你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 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)问题,是算法与编程领域内一个基础且经典的动态规划问题。它关注于在一个给定的无序序列中,如何高效地找到一个最长的单调递增的子序列(即每个元素都不...
除了动态规划之外,还可以使用其他方法解决最长上升子序列问题,比如使用二分查找的方法来改进动态规划的效率,使得时间复杂度从O(n^2)降低到O(nlogn)。这种方法被称作Patience Sorting算法,是一种基于分而治之的...
最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...
输入序列,求最长上升子序列的长度,算法复杂度nlgn
最长上升子序列问题是计算机科学和算法设计中的一个经典问题,它属于动态规划领域。在给定一个未排序的整数数组,最长上升子序列问题要求找出数组中最长的严格递增子序列的长度。例如,在序列[10, 9, 2, 5, 3, 7, ...
最长上升子序列问题(Longest Increasing Subsequence, 简称LIS),是计算机科学领域中一种经典的动态规划问题,主要用来求解一组数中的最长上升子序列的长度。所谓“上升子序列”,指的是序列中任意两个相邻的数...
- 第二段代码中同样使用动态规划,其中用f数组来保存每个位置的最长上升子序列长度,并在每次更新时寻找当前的最大值。 2. 动态规划(Dynamic Programming,简称DP): - 动态规划是一种算法思想,用于求解具有...
在计算机科学与算法设计领域,最长上升子序列问题是一个经典的动态规划问题,同时也有基于动态规划的改进方法。该问题的目标是在一个无序的整数序列中找出一个最长的上升子序列,即子序列中的数字是单调递增的。以下...
最长上升子序列(Longest Increasing Subsequence,简称LIS)是一个经典的计算机科学问题,属于动态规划领域的范畴。在这个问题中,给定一个未排序的整数数组,我们要求找出数组中最长的上升子序列。一个子序列是指...