Any time bounds on this problem?

The only sollution I could think of was the naive version...
and it has a runtime of O(n^2).

Which isn't a very good upper bound, anyone come up with anything better?

On the other hand, 500*500 = 250,000...
Which doesn't really make a difference on any machine that it will run on. Personally, I think you'll see a lot of solutions that solve the problem in the exact same number of steps. Any enlightenment on this issue?

I was thinking about this two, as far as i can tell it shouldnt take more than (2n-3) flips. but to decrease the number of flips would require a more intellegent algorithm, and probably take up extra time proccessing the most optimum flips thus decreasing the number of flips total... but increaseing the time it takes for the script to run. so its a trade off. but if you can figure out a mathmatical way to determine the number of minumum flips without actually running through the flipping of the array i would do that.

In some paper I read that there's an algorithm that takes (5n+3)/3 moves, but (unfortunately ;)) I'm not able to find the actual algorithm.

It's worth noting, though, that in many cases, if you do the 2n-3 algorithm (find largest, flip to top, flip to bottom), you'll end up with a solution that's far from being optimal. Even the simple example in the mission statement takes 5 moves, while it's obviously possible to do it in 3. I guess it's similar with the (5n+3)/3 algorithm...