List of integers & L.I.S.

[n00m]

sp1d3rx at gmail.com wrote:
> So, this has no real world use, aside from posting it on a website.
I don't think you're quite right.
We never know where we gain and where we lose.

> So clearly it served a very useful purpose!  ;)
Thanks, Manuel!

> your question is different than the question on this website.
Not exactly so (maybe I'm wrong here). How I did it (but got TLE
- Time Limit Exceeded (which is 9 seconds)).

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

4 5 1 2 3 6 7 8   << the list itself
1 2 1 2 3 4 5 6   << ordering numbers for forward direction
2 1 6 5 4 3 2 1   << ordering numbers for backward direction
===
3 3 7 7 7 7 7 7   << sums of the pairs of ord. numbers

Now those numbers with sum_of_ord.pair = max + 1 = 6 + 1
are the answer.
So the answer for your sample is: 1 2 3 6 7 8

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/