sagarsingla_'s blog

Longest Increasing Sub-sequence
By sagarsingla_, history, 5 years ago, In English

I need help in finding Longest Increasing Sub-sequence in minimum Time complexity.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sagarsingla_ (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

https://cp-algorithms.com/sequences/longest_increasing_subsequence.html

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Did you find any?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The minimal possible complexity is $$$O(n\log \log \text{LIS})$$$. But it's very hard (van Emde Boas trees). The optimal complexity for CP is $$$O(n\log n)$$$.

P. S. https://hal-upec-upem.archives-ouvertes.fr/hal-00620279

→ Reply