JavaScriptで増加するシーケンスを含む2Dの最長パス

シーケンスの増加

後続の各要素が前の要素以上である数列は、増加するシーケンスです。

たとえば、

4, 6, 8, 9, 11, 14 is increasing sequence
3, 3, 3, 3, 3, 3, 3 is also an increasing sequence

問題：

唯一の引数として、数値の2次元配列arrを受け取るJavaScript関数を作成する必要があります。この関数は、増加する数値のみを含む配列内の最長パスの長さを見つけて返す必要があります。

たとえば、関数への入力が-

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));

コードの説明：

アイデア

• ここでは、バックトラッキング深さ優先探索を使用しました。

• 再帰関数は、指定された行と列の最長増加パスを返すだけです

• ポジションの最長増加パスの記録がすでにある場合は、それを返すだけです。

出力

そして、コンソールの出力は-

4