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

[Tim Peters]

[Tim Peters, on the problem at
     http://spoj.sphere.pl/problems/SUPPER/
]
>> ...

[n00m at narod.ru]
> INCREDIBLE~
> 241433 2005-09-11 04:23:40 Tim Peters accepted  3.44  7096  PYTH
> BRAVO!

It's different now ;-)  I added the two lines

import psyco
psyco.full()

and time dropped to 2.29, while memory consumption zoomed:

    2005-09-11 18:44:57 Tim Peters accepted  2.29  42512  PYTH

That surprised me:  my own test cases on Windows using Python 2.4.1
enjoyed the same order of speedup, but barely increased RAM usage. 
Perhaps they installed an older (or newer <0.9 wink>) version of
psyco.

> I just wonder have I grey cells enough for to understand how your
> algo works...

You do!  Work out some small examples by hand, and it will become
clear; be sure to read the comments before the code, because they
explain it.

> and hopefully it's not your last solved problem on the contester.

I have to stop now, else I wouldn't do anything else <0.3 wink>.

> ...