JavaScript에서 증가하는 시퀀스를 포함하는 2차원에서 가장 긴 경로

<시간/>

증가 시퀀스

각 후속 요소가 선행 요소보다 크거나 같은 숫자 시퀀스는 증가 시퀀스입니다.

예를 들어,

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

코드 설명:

아이디어

여기서는 역추적 깊이 우선 검색을 사용했습니다.
재귀 함수는 단순히 주어진 행과 열에 대해 가장 긴 증가 경로를 반환합니다.
위치에 대한 가장 긴 증가 경로에 대한 레코드가 이미 있는 경우 이를 반환하면 됩니다.

출력

콘솔의 출력은 -