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

[Bryan Olson]

n00m wrote:
 > Oops Bryan... I've removed my reply that you refer to...
 > See my previous - CORRECT - reply. The code just times
 > out... In some sense it doesn't matter right or wrong is
 > its output.

If my code times out, then they are using an archaic platform.
With respect to my code, you noted:

     Bravo, Bryan! It's incredibly fast!

I myself did not claim 'incredibly fast'; but the code should
beat the 9-second mark on any currently-viable platform, even if
the machine were bought on special at Wal-Mart.

For this kind of low-level challenge, Python cannot compete with
the speed of C/C++, nor Ada, Pascal, ML, PL/1, nor even good
Java implementations. Nevertheless, even in the rare cases in
which efficiency of such computations is an issue, the Python
solution is usually worthy contender, and often the superior
solution.

Human time is more valuable than machine time. Python emphasizes
human-friendly code.


Alas, I would be (and, since I did cite it, was) wrong on that.
My code failed for the empty sequence. Wheter or not that was
one of the test cases, and whether or not it was a consideration
as the problem was defined, it was a bug. As I wrote:

     Good programmers own their bugs.


 > Btw, what is the complexity of your algorithm?

For a list of n items, time Theta(n ln(n)), space Theta(n).


-- 
--Bryan