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? -- http://mail.python.org/mailman/listinfo/python-list
