×

# Is there any algorithm for "Longest increasing subsequence" with complexity less than O(n^2)?

 2 I just want to know that while using dp for Longest increasing subsequence we get a complexity of O(n^2). Is there any other algorithm by which we can reduce the complexity??? Please explain the algo if it exists. asked 20 Jun '14, 22:55 224●2●4●8 accept rate: 33% Yes, there is an O(nlogn) solution for LCIS. If you want to know the length, it just takes O(n) space. But if you need to print the sequence, it MIGHT take O(n^2) space :) (21 Jun '14, 00:13) wiseboy2★

 2 You can refer this post on geeksforgeeks. It provides an nlogn solution for LIS. This question on stackoverflow also explains the nlogn approach very well. Take a look at this link also. answered 21 Jun '14, 00:12 4★roman28 1.6k●7●14●29 accept rate: 19%
 0 There is an O(nlogn) algorithm for longest increasing subsequece, see the link lis answered 21 Jun '14, 00:07 2★phenom 1 accept rate: 0%
 0 Yes, there is an O(nlogn) solution for LCIS. If you want to know the length, it just takes O(n) space. But if you need to print the sequence, it MIGHT take O(n^2) space :) answered 21 Jun '14, 00:13 2★wiseboy 129●1●10 accept rate: 0%
 0 Yes, there is an O(nlogn) solution . You can use segment tree or fenwick tree. For more details you can read this blog https://www.quora.com/What-is-the-approach-to-find-the-length-of-the-strictly-increasing-longest-subsequence. answered 16 Jul '15, 13:41 2★tirthtp 28●1●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,714
×2,165
×1,655
×204
×141

question asked: 20 Jun '14, 22:55

question was seen: 6,371 times

last updated: 16 Jul '15, 13:41