|   登录   |   注册   |   设为首页   |   加入收藏   

用户登录

close

用户名:

密码:

新用户注册

close

用户名:

密码:

密码确认:

电子邮箱:

关注内容:

个人主页:

帮助

close

龙宇网成立于2008年3月,网站进入整体运作于2010年10月1日。

在这里,我们把它做成了一个真正意义上的网站,完全以个人的信息为内容,以网友的需要为主导,全力搜罗各种信息,建立完善的网站功能,使网友在这里可以第一时间找到所需要的信息。

现在,经过三年的努力,网站的资料已经相当丰富,而网站得到了大家的喜爱和认可。

但,我们还是会继续努力下去,让网间的这份快乐继续持续下去,让这份闲暇时的日子,与快乐一并同行。

寻觅快乐,网住快乐,关注网络,是龙宇网的宣言与承诺。

问题: leetcode-Longest Increasing Subsequence

发布时间:2015-11-03 21:56:13 浏览次数:785


Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the

length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

给定无序的整数数列, 找出长度最长的递增子序列
示例:
给定无序序列【10,9,2,5,3,7,101,18】
最长的递增子序列式【2,3,7,101】, 因此长度是4。可能有多个子序列, 只需要返回长度就可以了。
你的算法时间复杂度可以为O(n2) ,是否可以找到O(nlogn)时间复杂度的算法。
 



回答

解题思路:

采用动态规划,O(n2) 的时间复杂度。

 

 

标签: leetcode
18
16