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(n^{2})$.↵
↵
In given matrix of integers find subrectangle with largest sum. It can be solved in $O(n^3)$.↵
↵
Can you give me links or just statements on similar problems?↵
↵
Here problems that i remembered:↵
↵
- [Count of subrects with max-min<=K](http://mirror.codeforces.com/gym/100570/problem/C)↵
↵
- [Count of subrects with ones<=K](http://mirror.codeforces.com/contest/364/problem/E)↵
↵
- [Largest arithmetic subrect](http://mirror.codeforces.com/gym/100523)↵
↵
- [Count of all zero-subrects](https://www.hackerrank.com/challenges/demidenko-farmer)↵
↵
- [Count of squares with exactly K stripes](http://acm.timus.ru/problem.aspx?space=1&num=2039)↵
↵
- [Largest subrect in 01-matrix with zero-perimeter](http://usaco.org/index.php?page=viewproblem2&cpid=600)↵
↵
↵
Please, gimme other problems, any links in contests or archives:) I will add it here later.
↵
In given matrix of zeros and ones find subrectangle that contains only zeros and has largest area. It can be solved in $O(n^{2})$.↵
↵
In given matrix of integers find subrectangle with largest sum. It can be solved in $O(n^3)$.↵
↵
Can you give me links or just statements on similar problems?↵
↵
Here problems that i remembered:↵
↵
- [Count of subrects with max-min<=K](http://mirror.codeforces.com/gym/100570/problem/C)↵
↵
- [Count of subrects with ones<=K](http://mirror.codeforces.com/contest/364/problem/E)↵
↵
- [Largest arithmetic subrect](http://mirror.codeforces.com/gym/100523)↵
↵
- [Count of all zero-subrects](https://www.hackerrank.com/challenges/demidenko-farmer)↵
↵
- [Count of squares with exactly K stripes](http://acm.timus.ru/problem.aspx?space=1&num=2039)↵
↵
- [Largest subrect in 01-matrix with zero-perimeter](http://usaco.org/index.php?page=viewproblem2&cpid=600)↵
↵
↵
Please, gimme other problems, any links in contests or archives:) I will add it here later.
