Hello,

I have been studying the problem of Longest Increasing Subsequence (N log (N)) from the GeeksForGeeks website, but it doesn't make sense to me, and I don't know if their code is right. Can someone explain the algorithm, and also provide working code? Also, can someone tell me how I can modify the code to work for nondecreasing sequences and provide working code? Also, how can I reconstruct the actual sequences? Thanks!

-dx24816

Let

Abe input array of sizeNand an auxiliary arrayminNumber, whereminNumber[x]represents the smallest possible last element for LIS of lengthxof the observed array.The idea behind the auxiliary array -

While iterating over

A, we want to keep track of all the Increasing Sequence possible. Now, at any point in time, we will have multiple increasing sequences of lengthxbut the one with smallest last value can generate sequences of lengthx+1which will include all possible increasing sequences which can be generated by any other sequences of the same length. Also, we are not much concerned about the non-last element of all the increasing sequences while appending a new element. So we can just store the smallest possible last element for an increasing sequence of lengthx.Note:

minNumberwill always be sorted.Now assuming 1-based indexing, assigning manually for the first element -

Now iterating over

A, for theith element. Let's saya = A[i]—If

ais not more thanminNumber[LIS], it is possible to reduce the last element of an existing length LIS. (BetterminNumber)Else we can have a new Longest Increasing Subsequence observed till now.

Clubbing them together -

Binary search

ainminNumber-Find the largest value which is smaller than(or equal for nondecreasing sequences)

a, and assignaat the next index ofminNumber. If next index doesn't exists, insertaand increasing theLIS;Finally, our solution will be value of

LIS.Some old snippet(Possibly working :p) -