Skip to content

Instantly share code, notes, and snippets.

@huichops
Created September 5, 2016 21:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save huichops/a1cf5d380e91143e79fc5c57c8ec1a4e to your computer and use it in GitHub Desktop.
Save huichops/a1cf5d380e91143e79fc5c57c8ec1a4e to your computer and use it in GitHub Desktop.
var longestIncreasingPath = function(matrix) {
if (matrix.length === 0) return 0;
if (matrix[0].length === 0) return 0;
var m = matrix.length;
var n = matrix[0].length;
var max = -99999
var memory = [];
for (var p = 0; p < m; p++) {
memory.push([]);
for (var q = 0; q < n; q++) {
memory[p].push(0);
}
}
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
var path = getLongestPath(matrix, i, j, -1, 0, memory);
if (path > max) max = path;
}
}
console.log(memory);
return max;
};
var getLongestPath = function(matrix, m, n, number, length, memory) {
var coords = [[0, -1], [0, 1], [1, 0], [-1, 0]];
var max = -9999;
if (m < 0 || m >= matrix.length) return 0;
if (n < 0 || n >= matrix[0].length) return 0;
if (number >= matrix[m][n]) return 0;
if (memory[m][n]) return memory[m][n];
for (var i = 0; i < coords.length; i++) {
var path = getLongestPath(matrix, m + coords[i][0], n + coords[i][1], matrix[m][n], length, memory) + 1;
if (path > max) max = path;
}
memory[m][n] = max;
return max;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment