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

Fri Sep 9 03:31:52 CEST 2005

```n00m wrote:

> Firstly I find ordering numbers when moving from left to the right;
> then I find ord. numbers for backward direction AND for DECREASING
> subsequences:

Sounds good.

> Btw, I did it in Pascal. Honestly, I don't believe it can
> be done in Python (of course I mean only the imposed time limit).
> http://spoj.sphere.pl/status/SUPPER/

Is there a platform specified? Below is an alleged solution in Python.

--
--Bryan

#!/user/bin/env python

"""
Python 2.4 solution to:

http://spoj.sphere.pl/problems/SUPPER/
"""

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])