List of integers & L.I.S. (SPOILER)

[n00m]

Bravo, Bryan!
Looks very neat! (pity I can't give it a try in my Py 2.3.4
because of reversed() and sorted() functions)
And I've submitted it but got ... TLEs:
http://spoj.sphere.pl/status/SUPPER/
Funnily, the exec.time of the best C solution is only 0.06s!

PS
In my 1st submission I overlooked that your code handles only
1 testcase (there are 10 of them); hence its 0.13s exec. time.
PPS
This is the code's text I submitted:


#!/user/bin/env python
from sys import stdin

def one_way(seq):
     n = len(seq)
     dominators = [n + 1] * (n * 1)
     # dominators[j] is lowest final value of any increasing sequence
of
     # length j seen so far, as we left-right scan seq.
     score = [None] * n
     end = 0
     for (i, x) in enumerate(seq):
         # Binary search for x's place in dominators
         low, high = 0, end
         while high - low > 10:
             mid = (low + high) >> 1
             if dominators[mid] < x:
                 low = mid + 1
             else:
                 high = mid + 1
         while dominators[low] < x:
             low += 1
         dominators[low] = x
         score[i] = low
         end = max(end, low + 1)
     return score

def supernumbers(seq):
     forscore = one_way(seq)
     opposite = [len(seq) - x for x  in reversed(seq)]
     backscore = reversed(one_way(opposite))
     score = map(sum, zip(forscore, backscore))
     winner = max(score)
     return sorted([seq[i] for i in range(len(seq)) if score[i] ==
winner])

for tc in range(10):
    _ = stdin.readline()
    sequence = [int(ch) for ch in stdin.readline().split()]
    supers = supernumbers(sequence)
    print len(supers) 
    for i in supers: 
         print i,