Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

adaptatron's blog

[Tutorial] : LIS using Trie : Longest Increasing Subsesquence
By adaptatron, 5 days 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
  • +3
  • Vote: I do not like it

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

So cool

→ Reply
»
5 days 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
  • »
    »
    5 days 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