Блог пользователя mkagenius

Longest Increasing Sequence , how to get the dp array we normally get in n^2 algo. using nlogn algo. ?
Автор mkagenius, 13 лет назад, По-английски
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.
Теги lis
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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])
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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...
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      It is right... but quite hard-written. look at this.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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.
        → Ответить