เส้นทางที่ยาวที่สุดใน 2 มิติที่มีลำดับที่เพิ่มขึ้นใน JavaScript

เพิ่มลำดับ

ลำดับของตัวเลขซึ่งแต่ละองค์ประกอบที่ตามมามีค่ามากกว่าหรือเท่ากับองค์ประกอบก่อนหน้านั้นเป็นลำดับที่เพิ่มขึ้น

ตัวอย่างเช่น

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

ปัญหา:

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ 2 มิติของตัวเลข 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));

คำอธิบายโค้ด:

ไอเดีย

• ในที่นี้เราได้ใช้การค้นหาย้อนหลังเชิงลึกก่อน

• ฟังก์ชันการเรียกซ้ำจะส่งกลับเส้นทางที่เพิ่มขึ้นที่ยาวที่สุดสำหรับแถวและคอลัมน์ที่กำหนด

• หากเรามีบันทึกของเส้นทางการเพิ่มขึ้นที่ยาวที่สุดสำหรับตำแหน่งแล้ว เราก็สามารถคืนค่านั้นได้

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

4