Thomas.Chang wrote: > I find that the common solution is to find the LIS (longest incremental > sequence) repeatedly. Generally it's a little complex. My solution is > as follows: > maintain a group array, in which each element is the last one in that > group(sequence); > for a new one, we just find the largest group element which is smaller > that the current. replace the group element with the current. for > example. > 4, (number sequence) --> 4;(group element) > 4, 1 --> 4; 1; > 4, 1, 5 ---> 4, 5; 1; > 4, 1, 5, 9 --> 4, 5, 9; 1; > 4, 1, 5, 9, 2 --> 4, 5, 9; 1, 2; > 4, 1, 5, 9, 2, 3 --> 4, 5, 9; 1, 2, 3; > it seems correct, but I cannot verify it. Can you help?
Yes, the greedy algorithm is correct. It is related to the solitaire game Patience and can also be used to find a longest increasing (or decreasing) subsequence. Here are two references http://en.wikipedia.org/wiki/Patience_sorting http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/patience.pdf --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
