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

[Bryan Olson]

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


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