C语言算法分析：求最长的递增数列
求最长的递增数列（Longest Increasing sequence， LIS）是一个比较常见的问题。
给定数列 10， 22， 9， 33， 21， 50， 41， 60， 80，那么 LIS 为 10， 22， 33， 50， 60， 80
分析思路： 假定 array［0， 。.n-1］为输入数据， LIS［i］为array［0， 。。.i-1］时的LIS （i 》0， i《= n），并且 array［i］是 LIS［i］的最后一个元素。
那么，LIS（i） = {1 + max（LIS（j））}， 其中， j 《 i， array［j］ 《= array［i］。
如果没有满足条件的j，LIS（i） = 1
方法1： 使用递归函数。
显然，这是一个时间复杂度高的方法，很多函数重复调用了。
方法2：把中间结果保下来，避免重复计算：
声明：本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人，不代表电子发烧友网立场。文章及其配图仅供工程师学习之用，如有内容侵权或者其他违规问题，请联系本站处理。
举报投诉
-
算法
+关注
关注
23文章
4608浏览量
92845 -
C语言
+关注
关注
180文章
7604浏览量
136714 -
递增
+关注
关注
0文章
3浏览量
6680
发布评论请先 登录
相关推荐
10个经典的C语言面试基础算法及代码
算法是一个程序和软件的灵魂，作为一名优秀的程序员，只有对一些基础的算法有着全面的掌握，才会在设计程序和编写代码的过程中显得得心应手。本文包括了经典的Fibonacci数列、简易计算器、回文检查、质数
发表于 11-20 15:18
工商网监
评论