### dx24816's blog

By dx24816, history, 7 months ago, ,

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

•
• +3
•

 » 7 months ago, # | ← Rev. 2 →   +5 Let A be input array of size N and an auxiliary array minNumber, where minNumber[x] represents the smallest possible last element for LIS of length x of 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 length x but the one with smallest last value can generate sequences of length x+1 which 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 length x. Note: minNumber will always be sorted.Now assuming 1-based indexing, assigning manually for the first element -  minNumber[1] = A[1]; LIS = 1; Now iterating over A, for the ith element. Let's say a = A[i] — If a is not more than minNumber[LIS], it is possible to reduce the last element of an existing length LIS. (Better minNumber) Else we can have a new Longest Increasing Subsequence observed till now. Clubbing them together -Binary search a in minNumber-Find the largest value which is smaller than(or equal for nondecreasing sequences) a, and assign a at the next index of minNumber. If next index doesn't exists, insert a and increasing the LIS;Finally, our solution will be value of LIS.Some old snippet(Possibly working :p) - int getLIS(vector &v) { ll N = v.size(); vector smallest(N); //index = maxlen-1 smallest[0]=v[0]; int mxlen=1; for(int i=1;ismallest[mxlen-1]) { // Change Here for nondecreasing smallest[mxlen++]=v[i]; } else { int k=lower_bound(smallest.begin(),smallest.begin()+mxlen,v[i])-smallest.begin(); // Change Here for nondecreasing assert(k>=0 && k