List of integers & L.I.S.
n00m
n00m at narod.ru
Wed Sep 7 18:48:52 CEST 2005
Given a list of N arbitrarily permutated integers from set {1..N}.
Need to find the ordering numbers of each integer in the LONGEST
increasing sequence to which this number belongs. Sample:
List:
[4, 5, 6, 1, 2, 7, 3]
Corresponding ordering numbers:
[1, 2, 3, 1, 2, 4, 3]
Details:
e.g. number 7 belongs to increasing sequence 1, 2, 7;
but this sequence is not the LONGEST sequence for "7".
The longest sequence for the 7 is 4, 5, 6, 7.
So, the 7's ordering number in this sequence is 4.
The salt of the thing is to do this with an O(n*log(n))
algorithm!
The straightforward O(n^2) algorithm is toooo slooow.
Any ideas?
More information about the Python-list
mailing list