On Mon, Feb 18, 2013 at 3:01 PM, Chris Angelico <ros...@gmail.com> wrote: > On Tue, Feb 19, 2013 at 8:54 AM, Ian Kelly <ian.g.ke...@gmail.com> wrote: >> Well, I don't see anything that looks especially slow in that code, >> but the algorithm that you're using is not very efficient. I rewrote >> it using dynamic programming (details left as an exercise), which got >> the runtime down to about 4 seconds. > > Did it involve a dictionary, mapping a value to its count, so that any > time you hit a value you've seen, you can short-cut it? That was my > first optimization consideration, though I didn't implement it in any > version, so as to keep the timings comparable.
Ayup. -- http://mail.python.org/mailman/listinfo/python-list
