Subrectangles problems

Revision en3, by Bugman, 2016-02-18 16:05:08

Hi people! I interested in problems with template name "Count of subrectangles" or "Best subrectangle" in rectangle. For example some well-known problems:

In given matrix of zeros and ones find subrectangle that contains only zeros and has largest area. It can be solved in O(n2).

In given matrix of integers find subrectangle with largest sum. It can be solved in O(n3).

Can you give me links or just statements on similar problems?

Here problems that i remembered:

Please, gimme other problems, any links in contests or archives:) I will add it here later.

Tags subrectangles, rectangles, problems, queries


  Rev. Lang. By When Δ Comment
en3 English Bugman 2016-02-18 16:05:08 69 new problem added
en2 English Bugman 2016-02-17 18:28:44 112
en1 English Bugman 2016-02-17 18:04:42 965 Initial revision (published)