Absolutely, this solution has O(n²) runtime for a problem that can be trivially solved in O(n).

After looking at the other answers, I feel stupid for not realizing this is n^3 :|

Who and (why upvoated) this answer? It's naive at best! You can easily solve this problem without nested loops (and many people have) which will perform much better for larger data sets. This isn't a best practice; it's broken. If I saw code like this in production, I'd stop whatever I was doing to fix it.

This is the reason why you do debug = nil before your tests xD

• Globals everywhere
• That's not what string.gsub is for
• Don't iterate arrays with pairs; use ipairs instead
• Table length is an expensive operation; don't use it in a while loop condition
• Flipping bits like that looks weird

This looks like C code

A sturdier initial value for max could be -math.huge, which is -inf when Lua was compiled with floating-point numbers.

Why not use ipairs though?

Technically your code is bugged. It works because of an implementation detail of both the test cases and the interpreter, but pairs doesn't iterate arrays in order. In this case, ipairs should be used instead.

You could also use the index when inserting into the result table, instead of re-calculating its length every time, which is an "expensive" operation. This would also fix the problem I mentioned above (Though I'd still recommend using ipairs, for several reasons)