You are not logged in. Please login at www.codechef.com to post your questions!

×

Is there any algorithm for "Longest increasing subsequence" with complexity less than O(n^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

megatron_64's gravatar image

4★megatron_64
224248
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★

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.

link

answered 21 Jun '14, 00:12

roman28's gravatar image

4★roman28
1.6k71429
accept rate: 19%

edited 21 Jun '14, 00:16

There is an O(nlogn) algorithm for longest increasing subsequece, see the link lis

link

answered 21 Jun '14, 00:07

phenom's gravatar image

2★phenom
1
accept rate: 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 :)

link

answered 21 Jun '14, 00:13

wiseboy's gravatar image

2★wiseboy
129110
accept rate: 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.

link

answered 16 Jul '15, 13:41

tirthtp's gravatar image

2★tirthtp
2814
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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