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

[n00m]

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
"""