So recently I was in an SRM, and was solving this problem, I will attach an image as it's not posted yet outside the applet.
http://imgur.com/sLxbFSV (^There is an option to zoom in).
Each element is between 0 and 255, and size of the array is at most 50.
Solution is Dynamic Programming in O(255*255*51*8).
After the round I got TLE, I thought it was maybe Java TLEing on a max case, but instead it looks like I TLE'd on a case where n = 5 ( lol ) yet my code passes for cases where N is nearly 50. C++ as copy paste from java passes all tests in around 300ms.
Now how can my code be passing cases where N is nearly 50 yet TLE on this one ? It just doesn't make sense...I did run it on my own machine, and it was fine.
A red guy on my room as well couldn't find anything wrong with, and just said it's weird. That's why I'm here CF :).
I can see why this code might TLE because of a large amount of calling functions in side the recursion code, I just don't get how it happens when n = 4...
Incase you would like to have a look at the code, here you go :
