p[i] maintains previous index from which b[i] has reached longest sequence till i. to get the actual list of non-decrease sequence, p has to be traversed through back indices for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
surender On Sat, Jul 16, 2011 at 9:06 AM, Neeraj Gupta <[email protected]>wrote: > > > Hi > >> Can anyone help me in understanding the following code >> http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp >> >> I am not able to understand what is the exact purpose of vector p in the >> above mentioned code. >> A little detail explanation will be helpful. >> >> I have already read this the basic idea of the algorithm > > * Let Ai,j be the smallest possible tail out of all increasing > subsequences of length j using elements a1, a2, ... , ai. Observe that, > for any particular i, Ai,1, Ai,2, ... , Ai,j. This suggests that if we > want the longest subsequence that ends with ai + 1, we only need to look for > a j such that Ai,j < ai + 1 < = Ai,j + 1 and the length will be j + 1. > Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and all Ai + > 1,k will be equal to Ai,k for k!=j+1. Furthermore, there is at most one > difference between the set Ai and the set Ai + 1, which is caused by this > search. Since A is always ordered in increasing order, and the operation > does not change this ordering, we can do a binary search for every single a > 1, a2, ... , an. > * > >> ~Neeraj >> > Hi, > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
