首页 > 试题广场 >

Longest Increasing Subsequence

[单选题]
Longest Increasing Subsequence (LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2, 1, 4, 2, 3, 7, 4, 6} is {1, 2, 3, 4, 6}, and its LIS length is 5. Considering an array with N elements, what is the average time and space complexity to get the length of LIS? 
  • Time: N^2, Space: N^2
  • Time: N^2, Space: N
  • Time: NlogN, Space: N
  • Time: N, Space: N
  • Time: N, Space: C
添加回答
推荐
牛客-007头像 牛客-007
答案：C
最长递增子序列，可以用动态规划（DP）算法来求解。
动态规划相当于递归的改进版，就是用辅助数组记录求解的中间过程来减少计算量。
需要一个长度为N的辅助数组记录当前子串的最长递增子序列的长度。
平均时间复杂度为NlogN，空间复杂度为N
编辑于 2015-01-12 21:51:55 回复(0)
菜小豆头像 菜小豆
(1)算法导论上使用的经典动态规划（DP）算法，时间复杂度为O(n^2),空间复杂度为O(n)
(2)使用一个辅助的数组后，时间复杂度能达到O(nlogn),
我是勤劳的搬运工^_^!
编辑于 2015-09-03 09:54:54 回复(0)
老木子头像 老木子
最佳算法O(nlongn)

详见牛课堂算法第一讲第一题，左神讲解
发表于 2016-08-31 14:02:53 回复(0)
小南坑头像 小南坑
我说我是看他特别，才蒙对的你们信吗..?
发表于 2019-03-15 14:26:10 回复(1)
提交观点

问题信息

复杂度
来自：微软2014校招研发工...
上传者：小海豹
难度：
4条回答 5208浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号