mkagenius's blog

Longest Increasing Sequence , how to get the dp array we normally get in n^2 algo. using nlogn algo. ?
By mkagenius, 13 years ago, In English
Can someone explain how do to get the array of LIS , that is the dp[] array we normally get in LIS using n^2 algo. using nlogn algo. that is patience sort ? Thanks.
Tags lis
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Look at array dp[]. You can see that it is sorted array, so you can use binary search when you want to find dp[i].
So it takes O(NlogN) time
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    dp[] array is not made until we use n^2 algo, then where to binary search.
    I think I did not make it clear:
    dp[i] is the array of LIS lengths starting at ith element.
    (starting means the first element of the LIS is a[i])
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Look: dp[i] is the length of maximum increasing subsequence. And, of course, by increasing i, dp[i] also increases, so that dp[i]  ≤  dp[i + 1]. Because when length of array A increases, probability of longer increasing subsequence also increases. So, when you are going to find dp[i], you can use binary search. Like this:
      l = 0; r = i - 1;
      if (a[(l+r)/2] <= a[i]) search((l+r)/2, r); else search(l, (l+r)/2);
      something like this...
      try to analyze some examples...
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Can you plz verify my code , is it what you are saying ?
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    By the way , I found a way of doing it, it was not that difficult as I thought.
    http://ideone.com/tHksB
    it stores the longest decreasing subsequences's length from backwards.
    It can be modified to find LIS also i guess.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It is right... but quite hard-written. look at this.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        what you are storing in d[] is completely different than what I am storing in dp[].
        Your is itself a longest increasing sequence.
        But My dp[] is actually , the " lengths " of LIS ,
        your d[] and my vec are same thing.
        But I wanted the dp[].
        Thanks for trying to help, but my doubt is clear now.
        Thanks again.
        → Reply