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}}