❶ c语言，最长上升子序列数,,
最长上升子序列（LIS）
问题描述：设现在有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。
示例：1 7 3 5 9 4 8 结果为4
题例：参看POJ 2533
解法：
1. DP之O(n2)算法：先按DP的思想来分析一下，要想求n个数的最长上升子序列，设有数据数组data[n]和状态数组dp[n]，则对其尾元素data[n]来说，它的最长上升子序列就是它自己，即dp[n]=1，而当把它的前一个元素data[n-1]考虑进来时，如果data[n-1]<data[n]则会存在一个长度为2的上升子序列，如果data[n-1]>data[n]那么这个长度仍会是1。当把这个思想一般化的时候，对于任意一个元素data[k]来说，我们需要找出在data[k]以后的元素中比data[k]大，并且最长的一个序列做为它的后继。这样dp[k]就可以写成dp[k+1]+1。现在我们定义一个量dp[k]=m，它代表着到第k个元素为止（可以包含k也可以不包含k），它的最长上升序列的长度为m。仔细体会dp[k]=m的意义，这里面的k是可包括在内，也可以不包括在内的（与之前的最大子序列和不同）。要想确定这个m的值，就必须找到一个在第k个元素之前的一个元素的值小于data[k]的值，并且那个元素所对应的dp值是找到的满足第一个条件前提下dp值最大的一个。这就意味着我们需要内层遍历之前算出来的dp值，所以需要两层循环来实现这个算法。这样我们就可以总结出状态转移方程为dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的过程我们需要用一层循环来实现，而找dp[k]的过程也要一层循环，所以我们得到了O(n2)的算法。
dp[k]=max(dp[i])+1 其中i满足(1<=i<=k&&a[i]<a[k])
例程：
#include <stdio.h>
const int inf = -0x3fffffff;
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1};
len = sizeof(data)/sizeof(int);
res = max = inf;
for(i=1;i<len;i++)
{
max = inf;
for(j=0;j<=i;j++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j];
dp[i]=max+1;
if(res<dp[i])
res = dp[i];
}
printf("%d\n",res);
return 0;
}
❷ 求问C语言：简易版最长序列
#include<stdio.h>
voidfun()
{
intn,m,max=0,a[10]={0};
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
a[m]++;
}
for(m=0;m<10;m++)
if(a[m])
{
if(a[m]>max)
max=a[m];
}
for(m=0;m<10;m++)
if(a[m]==max)
printf("%d%d ",m,a[m]);
}
intmain()
{
intt;
scanf("%d",&t);
while(t--)
{
fun();
}
return0;
}
❸ 设计一个O（n的平方）时间的算法，找出由n个数组成的序列的最长单调递增子序列
用冒泡法 时间复杂度=O(n^2)
以 下是c语言版
#include <stdio.h>
main()
{int a[10];
int i,c,j;
for(i=0;i<10;i++)
{printf("请输入十个数,这是第%d个:",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
for(j=10;j>i+1;j--)
{if(a[j-1]<a[j-2])
{c=a[j-1];
a[j-1]=a[j-2];
a[j-2]=c;
}
}
}
printf("从小到大的顺序是:");
for(i=0;i<10;i++)
{printf("\n%d",a[i]);
}
getch();
}
❹ c语言求最长递增序列
int findLengthOfLCIS(int* nums, int numsSize){
if(numsSize <=1 )
{
return numsSize;
}
int ans, cnt, i;
ans = 1; //保存最长数
cnt = 1; //记录最长数
for(i=0; i<numsSize-1; i++)
{
if(nums[i+1]>nums[i]) //如果递增，计数加一，否则重新算起
{
cnt++;
}else{
cnt = 1;
}
ans = cnt>ans ? cnt: ans; //更新并保存之前最长数
}
return ans;
}
❺ c语言编写 求一个数列中的最长子序列 数字可以不连续 如 输入 8 4 5 7 6 1 输出 4
无限不循环小数
❻ C语言求最长子序列
下面是你的代码修改过后的结果，改过的地方都有注释，另有测试样例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最长子序列：9
4
-2 -3 8 -7
最长子序列：8
3
-2 -2 7
最长子序列：7
2
-1 5
最长子序列：5
1
-2
最长子序列：0
Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.
*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在这里再加一个判断条件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是负数的话，结果应该是0，即一个都不选
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最长子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
❼ C语言LCIS（最长公共上升子序列）（DP）如何打印解
用一个解向量存储解啊，思路如下
function(..., char v[]) /*v用于存储最优解的*/
{
......
if(当前解更优){
当前解为更优解;
更新向量v; /*最好附添加一个结束符*/
}
......
}
主函数中输出解向量即可。
❽ 最长非降子序列 C语言
任意数列为a[n];
用b[n]来记录最长递增子序列的长度；
代码如下：
int MaxSort()
{
int i, j, k;
for (i=1, b[0]=1; i<n; i++)
{
for(j=0,k=0; j<i; j++)
if (a[j]<=a[i] && k<b[j])
k = b[j];
b[i] = k+1;
}
//返回最大的b[i]
int tmp = 0;
for (int i=0; i<n; i++)
{
if (tmp < b[i])
tmp = b[i];
}
return tmp; //返回最长非降子序列的个数
}
***************************
如果是返回最长子序列，可以用容器：
vector<int > MaxSort()
{
int i, j, k;
for (i=1, b[0]=1; i<n; i++)
{
for(j=0,k=0; j<i; j++)
if (a[j]<=a[i] && k<b[j])
k = b[j];
b[i] = k+1;
}
//返回最大的b[i]的下标count
int count= 0, tmp = 0;
for ( i=0; i<n; i++)
{
if (tmp < b[i])
{
tmp = b[i];
count = i;
}
}
//定义vector,存最长非递减子序列
vector<int> vec;
tmp = b[count];
for ( i=count; i>=0 ; i--)
{
if (tmp >= b[i])
{
vec.push_front(b[i]);
tmp = b[i];
}
else
break;
}
return vec;
}
❾ 求问c语言最长公共子序列代码哪里错了！！！ 搞了好久，头晕了都。 感觉是对的，就是不行。。。
楼主你好。
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[8][7],int b[8][7])
{
int i,j;
//下面两行不怎么需要，因为已经初始化为0了
for(i=0;i<m;i++) c[i][0]=0;//注意应该是从0到m-1
for(i=0;i<n;i++) c[0][i]=0;
for(i=1;i<m;i++){//这里注意应该是从1到m-1
for(j=1;j<n;j++){
if(x[i]==y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}else {
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void printMatrix(int matrix[8][7]){
int i,j;
for(i=0;i<8;i++){
for(j=0;j<7;j++){
printf("%d ",matrix[i][j]);
}
printf("\n");
}
}
void LCS(int i,int j,char *x,int b[8][7] )
{
if(i==0||j==0) return;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
printf("%c\n",x[i]);
}else if(b[i][j]==2){//这里注意是==，不是=
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
int main()
{
int c[8][7]={{0}};
int b[8][7]={{0}};
char X[8]={' ','A','B','C','B','D','A','B'};
char Y[7]={' ','B','D','C','A','B','A'};
LCSLength(8,7,X,Y,c,b);
printf("Matrix c\n");
printMatrix(c);
printf("Matrix b\n");
printMatrix(b);
printf("最大公共子序列长度为%d\n",c[7][6]);
LCS(7,6,X,b);
return 1;
}
你运行一下我的代码，没问题的。代码中出现的问题我以注释的形式写出来了。
不过劝告楼主，以后写代码一定要多写一些注释。因为一般的程序员都能写出机器能读懂的代码，而高级程序员才能写出人也能读懂的代码。写注释很重要，显示出代码的思路。否则思路不清晰的高深代码，一开始只有原作者和上帝能懂，过一段时间就只有上帝能懂了。
如果还有问题可以再问。
❿ 求最长公共子序列的C语言程序
得到字符串m1,m2后，有一个为空则子列为空。
如果都不为空，开始下面的步骤。
求得两列的长度分别为n1,n2。
动态生n2行n1列矩阵（二维数组）。
取m2中每个元素（记位置为i）与m1中元素（记位置为j）逐个比较，如果相等则为矩阵中相应行列坐标的元素赋值为1，否则为0（可用循环嵌套完成）。
比如m1(abc0cbad)m2(cba1abc)两串的话，可以得到如图所示矩阵。
然后，不难看出，要进行如下步骤。
定义max,用来记录最大子列中元素个数。
定义数组l[n2],用来记录最大子列的首字符地址（因为可能有不同最大子列，故用数组，而不是单个变量）。
判断矩阵中每一个元素，是否为1，如果是则记下此时行地址到l数组，然后判断相对于这个元素的下一行下一列的元素是否为1，如果是则继续判断，一直到为0。记下此次判断（即一个while循环）中“1”的个数n，存入变量max。
对于矩阵中的每一个元素都这么判断，如果判断中n的值大于max那么把n付给max，同时把这个子列的首地址付给l[0]，l[0]后面的元素全赋值为-1。如果，某次判断得到的n与max相同，即有相同最大子列，那么把它的首地址存入l数组的下一个位置。
当这个矩阵的每一个元素都判断完毕后，会得到max,和数组l，然后用循环做如下输出过程：依次以l数组中的每个元素为首地址，输出m2字符串中以相应序号开头的max个字符，那么完成所有最大子列的输出。
昨天失眠了，一直到今天凌晨3点多，脑袋浑浑噩噩的，本想帮你敲代码，可是脑力不支了，估计敲出来也乱，还有问题的话，再讨论452032545