Find max-size sorted submatrix using dynamic programming

Question

i'm trying to solve a dynamic programming problem, consisting in having a matrix, find the max-size sorted submatrix.

I want to use dinamic programming to find the solution, but I don`t get the correct result.

My program consists in two methods: the first one checks recursively near elements to the position given by parameter. Then, in the second method, I call the previous one to find the max order of a submatrix, but it doesn't return the correct result.

For example, for this matrix and calling the class with new Solution(5, 6)

                10, 1, 4, 1, 4, 0
                1, 2, 10, 6, 2, 1
                6, 7, 20, 10, 1, 2
                9, 10, 23, 0, 3, 5
                10, 11, 24, 1, 0, 2

It should return 4. Here is my code:

import java.util.Scanner;

public class Solution {
    private int[][] mat;
    Scanner sc = new Scanner(System.in);
    int n, m;


    public Solution(int n, int m) {
        this.n = n;
        this.m = m;
        mat = new int[n][m];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                mat[i][j] = sc.nextInt();
        for(int i = 0; i < n; i++) {
            System.out.println();
            for(int j = 0; j < m; j++)
                System.out.print(mat[i][j] + "\t");
        }
    }

    public void call() {
        int sol = maxSortedMatrix(mat);
        System.out.println("Matrix of order " + sol);
    }

    private int nearElements(int i, int j, int[][] mat, int[][] maxLongi) {
        // basically recursively check surrounding elements. If they are exist and smaller than
        // current element, we should consider it as the longest increasing sub sequence. However if we
        // already check one element, the value corresponding to that index pair should no longer be zero,
        // thus no need to recursively calculate that value again.
        if (maxLongi[i][j] == 0) {
        // have not been visited before, need recursive calculation
            // have not recursively checking.
            int length = 1;
            // up
            if (i - 1 > -1 && mat[i][j] > mat[i - 1][j]) {
                length = Math.max(length, 1 + nearElements(i - 1, j, mat, maxLongi));
            }
            // down
            if (i + 1 < mat.length && mat[i][j] > mat[i + 1][j]) {
                length = Math.max(length, 1 + nearElements(i + 1, j, mat, maxLongi));
            }
            // left
            if (j - 1 > -1 && mat[i][j] > mat[i][j - 1]) {
                length = Math.max(length, 1 + nearElements(i, j - 1, mat, maxLongi));
            }

            // right
            if (j + 1 < mat[0].length && mat[i][j] > mat[i][j + 1]) {
                length = Math.max(length, 1 + nearElements(i, j + 1, mat, maxLongi));
            }
            maxLongi[i][j] = length; // setting maxLenTailing value here to avoid additional recurssively checking
            return length;
        }
        return maxLongi[i][j];
    }

    private int maxSortedMatrix(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0] == null || mat[0].length == 0) {
            return 0;
        }
        int[][] maxLength = new int[n][m];
        // store the max length of increasing subsequence that ending at i and j.
        int max = 0;
        // top left to bottom right
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
// scan every element in the matrix.
                maxLength[i][j] = nearElements(i, j, mat, maxLength);
                max = Math.max(max, maxLength[i][j]);
            }
        }
        return max;
    }
}

Answer 1

The problem is that your algorithm is wrong; you need a completely different one.

What your algorithm computes is the length of the longest increasing path through the matrix, namely 8:

              ,   ,   ,   ,   ,  0
              ,   ,   ,  6,  2,  1
              ,   , 20, 10,   ,  
              ,   , 23,   ,   ,  
              ,   , 24,   ,   ,  

It does this by computing, for each element in the matrix, the length of the longest increasing path that ends at that element:

             2,  1,  2,  1,  4,  1
             1,  2,  5,  4,  3,  2
             2,  3,  6,  5,  1,  3
             3,  4,  7,  1,  2,  4
             4,  5,  8,  2,  1,  2

and then selecting the greatest such length (namely 8).

Instead, what you need to do is compute, for each element in the matrix, the size of the largest sorted square submatrix that has that element at its bottom right:

             1,  1,  1,  1,  1,  1 
             1,  1,  2,  1,  1,  1 
             1,  2,  2,  1,  1,  1 
             1,  2,  3,  1,  1,  2 
             1,  2,  3,  1,  1,  1 

and then select the greatest such size (namely 3).

Note that, unlike the longest-increasing-path problem, this does not require recursion and memoization; rather, it's a pure dynamic programming problem. You can just work from the top to the bottom of the matrix, and from left to right, computing each subresult depending only on subresults that you've already computed. (I notice that you've tagged this question with [dynamic-programming], so I assume this is what your professor wants you to do.)

Answer 2

The answer for a square submatrix might be somewhat simpler to calculate than for a general rectangle. In Python, we can take advantage of a little trick with double comparisons (please see ruakh's answer for a general discussion):

a = [
  [10, 1, 4, 1, 4, 0],
  [ 1, 2,10, 6, 2, 1],
  [ 6, 7,20,10, 1, 2],
  [ 9,10,23, 0, 3, 5],
  [10,11,24, 1, 0, 2]
]

m = [ [1] * len(a[0]) for i in range(0,len(a)) ]

for i in range(1,len(a)):
  for j in range(1,len(a[0])):
    if a[i-1][j-1] <= a[i][j-1] <= a[i][j] and a[i-1][j-1] <= a[i-1][j] <= a[i][j]:
      m[i][j] = min(m[i-1][j],m[i][j-1],m[i-1][j-1]) + 1

for i in m:
  print i

"""
[1, 1, 1, 1, 1, 1]
[1, 1, 2, 1, 1, 1]
[1, 2, 2, 1, 1, 1]
[1, 2, 3, 1, 1, 2]
[1, 2, 3, 1, 1, 1]
"""