madcannibal's blog

LIS O(nlogn)
By madcannibal, history, 9 years ago, In English

i wish that anyone explains to me in simple way the algorithm of the Longest Increasing Subsequence in O(nlogn) time , cuz i actually read all online articles about it and found no one explain it well , thanks in advance :)

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i learned LIS from here. it's pretty good :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Is this possible to do binarysearch in an unsorted array?

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

the trick for the nlogn solution is to maintain, in addition to your dp table, an auxiliary table A so that A[ i ] holds the information "what is the minimum number in the array, such that an increasing subsequence of length i terminates at", it is easy to see that this array will be strictly increasing. Therefore, we can simply binary search the solution of every subproblem and update our array.

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

It is also worth mentioning that you can do LIS in O(n log n) time simply by improving the O(n^2) DP. Everything you need is coordinate compression and a Fenwick tree / interval tree. The code is longer than with the bsearching algorithm, but for many people the idea is simpler because it uses tools they already know.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it can be done without coordinate compression by processing in increasing order of value and using a segment tree in O(n log n).

    Edit: sorry for necroposting, didn't realise this blog was from 5 years ago.

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

Yes there is

Set implementation
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how to retain the LIS? This is fine for calculating its length. But what about the LIS itself?

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

      It's not possible with the set method, just use segment tree.

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

        Could you tell me how to retain LIS(sequence itself not the length) using segment trees?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Do the DP and find longest sequence with end value less than current value at index below us, augment the segment tree to return both max and index, then just step back the indices.

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

        It is possible with set. At each $$$i$$$, you should store the previous element's index in the LIS that contains $$$a_i$$$. For details see this comment.

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

      Here it is

      vector with binary search and finding LIS offline
      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It does not work if there are duplicates in a. e.g a = [1, 2, 3, 4, 1] It will give 3 but correct ans is 4

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

      Yes it is, sorry for not writting the notice

      Nondecreasing Longest Subsequence - With unique
      Nondecreasing Longest Subsequence - With duplicates
      Strict Increasing Longest Subsequence
      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Well yeah,there are a lot of articles and finally I found a video which explains the NlogN algorithm with an example step by step and the actual idea/logic behind it.You can refer it : https://youtu.be/nf3YG4CnTbg

→ Reply