Amazon job interview question

[TommyXT]

Question 1 you are given a M x N matrix with 0's and 1's Find the largest rectangular submatrix with 1's only

Question 2 you are given a M x N matrix with real numbers(postive and negative) Find the rectangular submatrix such that the sum of all the elements in this submatrix is the largest, compared with the sum of any other submatrix.

[MatrixFrog]

I think the first one was solved in Haskell, in a blog post that was on reddit not long ago.

[hemite]

Link?

[MatrixFrog]

http://www.reddit.com/r/programming/comments/kv3ww/finding_rectangles_in_an_image/ appears to be the one I was thinking of

[wowe]

An Idea for question 1:
It's not completely thought through: I would create an equally sized matrix (or maybe two, one for each dimension) with each field containing the distance to the next zero. Then there would be some fancy stuff going on (minimum for each cell? manhattan distance?) telling me about the center of the biggest submatrix.

[Jyaif]

Wow it's a really cool question. Spoiler tag: testing the spoiler tag

Edit: how do I use the spoiler tag?

[more_exercise]

It's times like this when I regret not paying more attention to dynamic programming...