单调递增最长子序列
时间限制:3000 ms | 内存限制:65535 KB
难度:4
描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
随后的n行,每行有一个字符串,该字符串的长度不会超过10000
3 aaa ababc abklmncdefg
1 3 7
思路:
题意简明易懂,所以不作解释。最基本的动态规划题,设 i 为当前位置,max[ i ]为当前位置的单调递增的最大长度,则max[ i ] = max{max[ i-1 ],max[ i-2 ],max[ i-3 ]......max[ 0 ]}+1(判断条件为s[ i ]>s[ ? ]),故算当前最大长度时,应设另外一个变量j从0开始到i进行遍历,找到最大的一项max [ j ]进行+1再赋值于max[ i ]。故 i 应从1遍历到length。数组中最大max[ i ]值即为最长递增子序列的长度。(一开始全部max数组的值都初始化为1)
AC:
#include<stdio.h> #include<string.h> int main() { int n,length,i,j,m; char s[10005]; int max[10005]; scanf("%d",&n); while(n--) { scanf("%s",s); length=strlen(s); for(i=0;i<length;i++) max[i]=1; //初始化为1不为0,因为最长子序列长度最坏的情况就是1 //即不存在这样的单调递增序列,每个数都是一个单独的递增长度,长度为1 m=1; //同理,最大值也应该是1,记得m的初始化在循环内进行,非循环外 //从前递推到后,i在前j在后,故判断条件应该是s[j]>s[i] for(i=1;i<length;i++) { for(j=0;j<i;j++) if(s[i]>s[j]) max[i]=max[i]>max[j]+1?max[i]:max[j]+1; //每个max[i]都为当前位置i为止的最大长度情况,但这不代表max数组最后一个值肯定为最大 if(max[i]>m) m=max[i]; //在最大值,无需另外开个循环再判断 } printf("%d\n",m); } return 0; }
总结:
在学新知识的时候应该找相对简单的题来练练手,以至于不生疏,于是大晚上的拿了道动态规划最基本的题来做。需要注意的地方还是有的,越简单出错的几率就越大,考虑循环边界的问题,还有最大值的初始化问题,这是之前一直出错的地方。
相关推荐
使用动态规划思想求出最长单调递增子序列(LIS),时间复杂度为O(n log k)
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
给定一个单调递增的整数序列,问某个整数是否在序列中
最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法
用动态规划方法找出由n个数a【i】(1)组成的序列的一个最长单调递增子序列
设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。
算法之动态规划---单调递增子序列,和图像压缩算法
T3: 单调递增最长子序列 T1: 拦截导弹 T2: 分弹珠 T5: 矩阵取数游戏 T2: 汽车加油问题 T3: 会场安排问题 T4: 程序存储问题 T1:自然数拆分问题 T2:自然数拆分的方案数 T3:子集和问题 T6:最短路径 T9:BFS
给定一个单调递增的整数序列,问某个整数是否在序列中
动态规划求 最长的单调递增子序列的题目,可。
L={a1,a2,a3,…,an},是由n个不同的实数组成的序列,求L的最长单调递增子序列的长度(下标可不连续)
最长单调递增子序列,使用动态规划算法,时间复杂度O(n2)
适合初学者,经典DP
算法导论,请给出一个O(n^2)时间的算法,使之能找出n个数的序列中最长的单调递增子序列
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
我写的LIS算法,有两种思路,程序全在这个cpp文件中,可以运行
RANDSPACE 生成一个单调递增的随机序列间隔值。 y = randspace(P1, N) 生成大于或等于 P1 的 N 个点点之间的间隔等于 [0,1] 中的随机值。 y = randspace(P1, N, P2) 在 P2 处切断生成的序列。 注意:如果设置了 P2,...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
数据结构与算法 c++实现 改变顺序表的元素次序,两个顺序表的元素严格单调递增,将其共同元素保存到新顺序表中,且为递增排序可直接运行 代码有批注 适合大二初学数据结构与算法