adaptatron's blog

[Tutorial] : LIS using Trie : Longest Increasing Subsesquence
By adaptatron, 2 months ago, In English

The problem of computing the length of the Longest Increasing Subsesquence is usually solved via DP, Binary Search or Segment Tree. I created a blog discussing a Trie based approach that can solve this problem with very few lines of code.

https://cfstep.com/training/tutorials/dp/lis-using-trie/

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So cool

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

I would argue that the segment tree solution is at least as good as the trie solution and they are equivalent for some segment tree implementations, but that is an interesting way of viewing it.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    An "infinite binary trie stored in a sparse way" is exactly a sparse segment tree. Still, it is cool that you were able to 'reinvent' it through a slightly different way of thinking.

    → Reply