given a 2-d matrix with 0 or 1 values
largest square of all 1‘s
dynamic programming, dp[i][j] = 1 + min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} if m[i][j] == 1; otherwise a[i][j]=0;
largest submatrix of all 1‘s
https://leetcode.com/problems/maximal-rectangle/
dynamic programming. scan row-by-row and accumulate the "height" at each position; then for each accumulated row, run the "largest rectangle in histogram" algorithm.
query sum of submatrix
https://leetcode.com/problems/range-sum-query-2d-immutable/
similar to prefix-sum array, generate sum[i][j] = sum{mat[0..i][0..j]}, then it‘s straightforward to answer sum of all possible submatrixes.
largest sum of submatrix
column-wise (i, j) sum (i.e. sum columns[i..j]), then solve 1-D case in O(n), in total O(n^3)
原文：http://www.cnblogs.com/qsort/p/6072073.html