Dynamic programming for longest increasing sequence in 2d array


  • 1
    L
    public class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
                return 0;
            }
            int[][] maxLenTailing = new int[matrix.length][matrix[0].length];
           // store the max length of increasing subsequence that ending at i and j.
            int maxLen = 0;
            // top left to bottom right
            for (int i = 0; i < matrix.length; ++i) {
                for (int j = 0; j < matrix[0].length; ++j) {
    // scan every element in the matrix.
                    maxLenTailing[i][j] = directionalCheck(i, j,matrix, maxLenTailing);
                    maxLen = Math.max(maxLen, maxLenTailing[i][j]);
                }
            }
            return maxLen;
        }
            private int directionalCheck(int i, int j, int[][] matrix, int[][] maxLenTailing){
        // 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 (maxLenTailing[i][j] == 0) {
    // have not been visited before, need recursive calculation
                    // have not recursively checking.
                int len = 1;
                // up
                if (i - 1 > -1 && matrix[i][j] > matrix[i-1][j]) {
                    len = Math.max(len, 1 + directionalCheck(i-1, j, matrix, maxLenTailing));
                }
                // down
                if (i + 1 < matrix.length && matrix[i][j] > matrix[i+1][j]) {
                    len = Math.max(len, 1 + directionalCheck(i+1, j, matrix, maxLenTailing));
                }
                // left
                if (j-1 > -1 && matrix[i][j] > matrix[i][j-1]) {
                    len = Math.max(len, 1 + directionalCheck(i, j -1, matrix, maxLenTailing));
                }
             
                // right
                if (j + 1 < matrix[0].length && matrix[i][j] > matrix[i][j+1]) {
                    len = Math.max(len, 1 + directionalCheck(i, j + 1, matrix, maxLenTailing));
                }
                maxLenTailing[i][j] = len; // setting maxLenTailing value here to avoid additional recurssively checking
                return len;
            }
            return maxLenTailing[i][j];
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.