`
synchronized_lala
  • 浏览: 41741 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
最近访客 更多访客>>
社区版块
存档分类
最新评论

最长上升子序列-动态规划

阅读更多

题目:

 设有一个正整数的序列: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

*/
1
4
分享到:
评论

相关推荐

    求出最长上升子序列中各个元素

    在算法领域,最长上升子序列(Longest Increasing Subsequence,LIS)问题是一个经典的问题,它在计算机科学中有着广泛的应用,例如在数据结构、排序算法以及动态规划等方面。本篇将详细介绍如何找出一个序列中长度...

    javascript-leetcode面试题解动态规划问题之第300题最长上升子序列-题解.zip

    本题解聚焦于LeetCode的第300题——最长上升子序列(Longest Increasing Subsequence, LIS),这是一个典型的动态规划问题。 动态规划是算法设计的一种策略,通过将复杂问题分解成更小的子问题来解决。在最长上升子...

    最长上升子序列最长上升子序列PDF

    最长上升子序列问题是一个经典的算法问题,通常在算法设计与分析、数据结构以及动态规划等领域中经常被提及。问题的核心是针对给定的序列,寻找一个最长的子序列,使得这个子序列中的任意两个元素按原有顺序比较都是...

    动态规划动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP

    动态规划概念 最长上升子序列 最长公共子序列 矩阵连乘问题 背包问题 树形DP 状态压缩DP

    8596 最长上升子序列

    本题通过动态规划的方法有效地解决了寻找最长上升子序列的问题。虽然时间复杂度为 \(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)动态规划解法的 Python 源码

    最长上升子序列(Longest Increasing Subsequence,简称LIS)问题,是算法与编程领域内一个基础且经典的动态规划问题。它关注于在一个给定的无序序列中,如何高效地找到一个最长的单调递增的子序列(即每个元素都不...

    leetcode-master-最长上升子序列

    除了动态规划之外,还可以使用其他方法解决最长上升子序列问题,比如使用二分查找的方法来改进动态规划的效率,使得时间复杂度从O(n^2)降低到O(nlogn)。这种方法被称作Patience Sorting算法,是一种基于分而治之的...

    什么是最长上升子序列,和最长不下降子序列有什么区别

    最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的...

    最长上升子序列nlgn源码

    输入序列,求最长上升子序列的长度,算法复杂度nlgn

    大一下_算法提高课-最长上升子序列

    最长上升子序列问题是计算机科学和算法设计中的一个经典问题,它属于动态规划领域。在给定一个未排序的整数数组,最长上升子序列问题要求找出数组中最长的严格递增子序列的长度。例如,在序列[10, 9, 2, 5, 3, 7, ...

    算法设计-最长上升子序列问题

    最长上升子序列问题(Longest Increasing Subsequence, 简称LIS),是计算机科学领域中一种经典的动态规划问题,主要用来求解一组数中的最长上升子序列的长度。所谓“上升子序列”,指的是序列中任意两个相邻的数...

    53、1281:最长上升子序列(A)+书画相关链接(十七)-2020.01.19.pdf

    - 第二段代码中同样使用动态规划,其中用f数组来保存每个位置的最长上升子序列长度,并在每次更新时寻找当前的最大值。 2. 动态规划(Dynamic Programming,简称DP): - 动态规划是一种算法思想,用于求解具有...

    求解最长上升子序列的方法

    在计算机科学与算法设计领域,最长上升子序列问题是一个经典的动态规划问题,同时也有基于动态规划的改进方法。该问题的目标是在一个无序的整数序列中找出一个最长的上升子序列,即子序列中的数字是单调递增的。以下...

    Algorithms-最长上升子序列

    最长上升子序列(Longest Increasing Subsequence,简称LIS)是一个经典的计算机科学问题,属于动态规划领域的范畴。在这个问题中,给定一个未排序的整数数组,我们要求找出数组中最长的上升子序列。一个子序列是指...

Global site tag (gtag.js) - Google Analytics