Largest submatrix problem 
Given a $N \times M$ matrix, I want to find the biggest submatrix, not necessarily a square one, that has the same value in all its entries.

For example, if $N=4$, $M=5$ and the matrix is 
$$\begin{bmatrix}1&2&3&4&5\\1&2&2&2&3\\4&2&2&2&6\\3&4&5&6&7 \end{bmatrix} $$
Then here the answer will be the submatrix
$$\begin{bmatrix}2&2&2\\2&2&2 \end{bmatrix} $$
So I need to find upper leftmost coordinate of this submatrix that is $[2,2]$ and bottommost right coordinate that is $[3,4]$.
 A: Here is an approach different from the one I gave in my comments that build upon your attempt, which is simply a different parametrization of the valid rectangles. In that parametrization a rectangle has (top-left,height,width) in that order, and the solution follows that.
Another parametrization is (top,bottom,left,right), and notice that for any (top,bottom) the valid rectangles are non-overlapping, so we can just scan one column at a time from left to right and try to extend the current rectangle, and once it fails we know that the next valid rectangle must have its left at the current column or later. Doing a little bit of preprocessing will enable us to query in $O(1)$ time for each column segment with given top and bottom, which I'll encourage you to figure out on your own; it's not hard. The preprocessing will take $O(mn)$ time and the rest will take $O(mn^2)$ time.
A: You'll find ruby code in the accepted answer for this here.
Though, the answer there is $\mathcal{O}(n^3)$, and I believe that it is possible to use dynamic programming to speed this one up considerably.
Update: Sorry, the link actually shows a DP version. The naïve implementation is $\mathcal{O}(n^4)$.
A: There is a simple idea is that
- For each unique value (V) in matrix A[n][m]
    - Split matrix into connected components of value (V)
    - For each connected component (C)
         - Find largest rectangle in (C)

For more details
- For each position [i][j] in matrix A[n][m]
- - - If (visit(i, j) = false)
- - - - - Bfs from (i, j) to get current component (C)
- - - - - - - While containing positions in queue
- - - - - - - - - Get the position and pop out of queue
- - - - - - - - - Mark current position as visited and add to (C)
- - - - - - - - - Only move to its neighbour (i ± 1, j), (i, j ± 1)
- - - - - - - - - If (neighbour in the matrix) and (equal to A[i][j])
- - - - - - - - - - - add this position to queue
- - - - - 
- - - - - For each position (x, y) in component (C)
- - - - - - - For each width (w) = 1 -> n
- - - - - - - - - If (this width is invalid) then break
- - - - - - - - - For each height (h) = 1 -> m
- - - - - - - - - - - If (this height is invalid) break
- - - - - - - - - - - - - Update result with (n * m)

There is such optimizations using data structures and binary search to optimize to about $O(n \times m \times min(n, m) \times log(max(n, m)))$ or even $O(n \times m \times min(n, m))$
Actually there is a simpler idea where we fix 2 rows then move for each columns and by using DP and data structure to calculate in $O(1)$ or $O(log)$. Therefore we can also achieve the same complexity
But with this idea, we can observe that

*

*For any column, if we move from lower row to higher row each step, then we can calculate the current "height" of a column, which is the furthest distance in column that every elements in it are equal, in $O(1)$


*For a fixed row $(x)$, if we can find maximum height for each column, then you can calculate the maximum rectangle area $S(x)$ that contain atleast one element in this row in $O(K(x))$ where $K(x)$ is the number of $(i, j)$ in $(C)$ that $(i = x)$
$\Rightarrow$ The maximum rectangle area in component $(C)$ is max of over all S(x) for all row $(x)$ existed in $(C)$. Which can be calculate in$ O(Σ(K(x))) = O(|C|)$
$\Rightarrow$ The complexity to calculate all component is $O(Σ(|C|)) = O(n \times m)$
