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

n00m n00m at narod.ru
Sun Sep 11 00:38:22 CEST 2005

```Bryan;
My own version also timed out.
And now I can tell: it's incredibly SLOW.
Nevertheless it would be interesting to compare
speed of my code against yours. I can't do it myself
because my Python is of 2.3.4 version.

Just uncomment "your" part.

import bisect

def oops(w,a,b):
for m in w:
j=bisect.bisect_left(a,m)
a.insert(j,m)
b.insert(j,max(b[:j]+[0])+1)

def n00m(n,w):
a,b=[],[]
oops(w,a,b)
v=map(lambda x: -x, w[::-1])
c,d=[],[]
oops(v,c,d)
e=map(sum, zip(b, d[::-1]))
mx=max(e)
f=[]
for i in xrange(n):
if e[i]==mx:
f.append(i+1)
print len(f)

def one_way(seq):
n = len(seq)
dominators = [n + 1] * (n * 1)
score = [None] * n
end = 0
for (i, x) in enumerate(seq):
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 + [0])
return sorted([seq[i] for i in range(len(seq)) if score[i] ==
winner])

def b_olson(sequence):
supers = supernumbers(sequence)
print len(supers)

import random, time
n=50000
w=range(1,n+1)
random.shuffle(w)

t=time.time()
n00m(n,w)
print 'n00m:',time.time()-t

"""
t=time.time()
b_olson(w)
print 'b_olson:',time.time()-t
"""

```