# Dynamic programming for longest increasing sequence in 2d array

• ``````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];

}
}``````

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