Puzzle of the week - Max Rect

Puzzles
#1

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!

#2

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

#3

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

#4

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.

#5

It’s actually what I’m doing, yet I still can’t pass that time out.
Do you have any tips?

Oh! I might have an idea …

#6

@olinox14 Actually it depends on what you call n.
If n = max(W,H), then O(n^3) is ok (but of course if n = W*H, then it’s not).

#7

Thanks @java_coffee_cup and @Niako for your answers (and sorry for the late reply). I managed to pass the validators since then: this was not a timeout in the end, but a mistake of mine in the adaptation of the Kadane’s subarray algo for a 2d array…
Thanks again!