JavaScript 中包含递增序列的二维最长路径

Z时代
2024-01-10
分类：综合

递增序列

每个后续元素都大于或等于前一个元素的数字序列是递增序列。

例如，

4, 6, 8, 9, 11, 14 is increasing sequence

3, 3, 3, 3, 3, 3, 3 is also an increasing sequence

问题：

我们需要编写一个 JavaScript 函数，该函数接受二维数字数组 arr 作为唯一参数。我们的函数应该找到并返回数组中只包含递增数字的最长路径的长度。

例如，如果函数的输入是 -

const arr = [
   [4, 5, 6],
   [4, 3, 7],
   [3, 3, 2]
];

那么输出应该是 -

const output = 4;

输出说明：

因为最长的递增序列是 4、5、6、7。

示例

此代码将是 -

const arr = [
   [4, 5, 6],
   [4, 3, 7],
   [3, 3, 2]
];
const longestIncreasingPath = (arr = []) => {
   let longest = 0;
   let dp = Array(arr.length).fill(null).map(() =>
   Array(arr[0].length).fill(1));
   const backtracking = (row, col) => {
      if (dp[row][col]!=1) return dp[row][col];
      let dRow = [1,0,-1,0];
      let dCol = [0,1,0,-1];
      for (let i = 0;i<dRow.length;i++) {
         let nR = row + dRow[i], nC = col+dCol[i];
         if (nR >= 0 && nR <arr.length&& nC >= 0 && nC < arr[0].length && arr[nR][nC] > arr[row][col]) {
            dp[row][col] = Math.max(dp[row][col], 1 + backtracking(nR, nC))
         };
      };
      return dp[row][col];
   }
   for (let i=0;i<arr.length;i++) {
      for (let j=0;j<arr[0].length;j++) {
         longest = Math.max(longest, backtracking(i, j));
      };
   };
   return longest;
};
console.log(longestIncreasingPath(arr));