Puzzle of the week - Max Rect


Hi, I’m currently doing th ‘Puzzle of the week - Max rect’, and even if all the tests pass, two of the after-submitting validators (3 et 4) keeps to fail…

Is there a way to know if those failures come from an error? A timeout?

I suspect a timeout, but I’m already using an O(3) algorithm and I don’t think that it could be faster…

Thanks by advance!


It’s a timeout because my O(n^3) Python script used to timeout too.


Seriously? More efficient than an O(n3) for that kind of algo? Do such thing exist?


Yes, such thing does exist.
Some people call it dynamic programming. Someone call it memorization. The principle is simple: if you know a + b = x, memorize it. When you want to calculate a + b + c, you should calculate x + c only. Never re-calculate the known fact (a+b). Then you have another known fact (a+b+c = y). Keep this in memory for future reuse.

Planning out how to implement it is another story. It can be challenging, interesting, and from time to time frustrating.