### mkagenius's blog

By mkagenius, 9 years ago, 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.  Comments (7)
 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
•  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])
•  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...
•  Can you plz verify my code , is it what you are saying ?
•  By the way , I found a way of doing it, it was not that difficult as I thought. http://ideone.com/tHksBit stores the longest decreasing subsequences's length from backwards.It can be modified to find LIS also i guess.
•  It is right... but quite hard-written. look at this.
•  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.