C语言实现最长递增子序列问题的解决方法
本文实例展示了C语言实现最长递增子序列问题的解决方法。分享给大家供大家参考。具体方法如下：
问题描述：
给定一个序列，找出其最长递增子序列长度。
比如 输入 1 3 7 5
输出 3
算法解决思路：
利用动态规划的思想，以序列的每个点最为最右端，找出每个点作为最右端时的子序列长度的最大值，即问题的求解。因此，在计算前面的每个点的时候，将其结果保存下来，后面的点与前面的点的数值进行比较，如果大，则在其长度基础上加1，并且找出所有可能情况下最长的保存为当前点的长度。形成递归。
具体实现代码如下：
#include "stdio.h"
#include "stdlib.h"
#define MAXDATA 10000
int main(){
int data[MAXDATA]; /*数据序列*/
int lgs[MAXDATA]; /*最长子序列长度*/
int n,temp,k; /*n 序列长度 temp 子序列长度中间变量 */
scanf("%d",&n);
if(n>10000){
return 0;
}
for(int i=0;i<n;i++){
scanf("%d",&data[i]);
}
for(int i=0;i<MAXDATA;i++){
lgs[i]=1; /*给每一个序列点作为右端时的最大序列长度为1*/
}
for(int i=1;i<n;i++){
temp=1;
for(int j=0;j<i;j++){ /*与其前面的每一个进行比较*/
if(data[i]>data[j]){ /*如果数据比前面的某一个的值大*/
if(lgs[i]+lgs[j]>temp){ /*找出该点的最大子序列长度*/
temp=lgs[i]+lgs[j];
}
}
}
lgs[i]=temp;
}
temp=lgs[0];
for(int i=1;i<n;i++){
if(lgs[i]>temp){
temp=lgs[i];
}
}
printf("%d",temp);
system("pause");
}
希望本文所述对大家C程序算法设计的学习有所帮助。
-
我为最长的递增子序列生成了以下代码： 输入：nums=[10,9,2,5,3,7,101,18] 输出：4 说明：最长的递增子序列是[2,3,7,101]，因此长度为4。 有人能帮我理解这句话吗 三个点的意义是什么？正如我们所知，映射生成键值对，映射与切片一起做什么？
-
我在阅读了允许K个异常的最长递增子序列后创建了这个线程。我意识到提问的人并没有真正理解这个问题，因为他指的是一个链接，该链接解决了“允许一次更改的最长递增子数组”问题。所以他得到的答案实际上与李的问题无关。 假设给定一个长度为N的数组A。查找允许K个异常的最长递增子序列。 示例：N=9，K=1 A=[3,9,4,5,8,6,1,3,7] 答案：7 说明： 最长递增子序列为：3,4,5,8（或6），
-
本文向大家介绍LIS 最长递增子序列 Java的简单实现，包括了LIS 最长递增子序列 Java的简单实现的使用技巧和注意事项，需要的朋友参考一下 今天遇到了一个求最长递增子序列的问题，看了之后就尝试着用Java实现了一下，关于什么是最长递增子序列，这里就不在赘述，可以百度或者Google之，以下为实现的代码： 说明：本段代码实现的功能为 （1）随机生成一个有10个元素的数组，然后输出它的最长递增
-
最长增子序列是我们熟知的问题，我用耐心算法给出了一个解决方案。 我曾想过先用我的算法，然后找到长度为N的第一个序列，但不知道该怎么做。 那么，如何从随机整数序列中找到第一个最长的递增子序列呢？ 我的代码段： 我的代码返回：1 2 8 第一个序列是：3 6 8 另一个例子： 我的代码正确返回：1 2 3 基本上，只要第一个最长序列与最佳最长序列相同，我的代码就能工作。但是当你有一堆相同长度的最长序列
-
在最多一个序列存在重复的情况下，可以将最长公共子序列问题转化为最长递增子序列问题。减少问题的过程说明在这里： 假设您有以下序列： 然后，创建一个整数序列S3，其中您必须将S2的每个元素的位置放在S1中（如果元素在S1中不存在，那么忽略那个元素）。在本例中： 这种方法是如何工作的？为什么这种约简解决了寻找最长公共子序列的问题？
-
本文向大家介绍C语言实现的排列组合问题的通用算法、解决方法，包括了C语言实现的排列组合问题的通用算法、解决方法的使用技巧和注意事项，需要的朋友参考一下 尽管排列组合是生活中经常遇到的问题，可在程序设计时，不深入思考或者经验不足都让人无从下手。由于排列组合问题总是先取组合再排列，并且单纯的排列问题相对简单，所以本文仅对组合问题的实现进行详细讨论。以在n个数中选取m(0<m<=n)个数为例，问题可分解