This is yet another Interview question of Media.net. Trying to apply dp on this is hard and I can't solve it. I looked up solutions on stackoverflow and GeeksforGeeks but they are all wrong. Can anyone give a correct approach or an idea on how to solve it please?

Problem: Given a matrix N by M, The task is to find the area wise largest rectangular sub-matrix such that each column and each row of the submatrix is strictly increasing

Example:
{{1, 2, 3},
{4, 5, 6},
{1, 2, 3}}

Output: 6

Explanation: The largest sorted submatrix is
{{1, 2, 3},
{4, 5, 6}}

Here are some cases in which the given solutions on the above mentioned sites fail

Case 1

{{1, 4},
{2, 3}}
Correct output: 2

Case 2

{{1, 2, 3},
{0, 5, 6},
{1, 2, 3}}
Correct output: 4

Explanation: The largest sorted submatrix is

{{2, 3},
{5, 6}}