JavaScript में बढ़ते क्रम वाले सबसे लंबे पथ की लंबाई

बढ़ता क्रम

एक संख्या क्रम जिसमें प्रत्येक अगला तत्व पिछले तत्व से बड़ा या बराबर होता है, एक बढ़ता क्रम कहलाता है।

उदाहरण के लिए,

4, 6, 8, 9, 11, 14 बढ़ता क्रम है 
3, 3, 3, 3, 3, 3, 3 भी एक बढ़ता क्रम है

समस्या:

हमें एक JavaScript फ़ंक्शन लिखना है जो संख्याओं के एक 2-D सरणी 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));

कोड व्याख्या:

विचार

यहां, हमने बैकट्रैकिंग डेप्थ फर्स्ट सर्च का उपयोग किया है।
पुनरावृत्ति फ़ंक्शन केवल एक दिए गए पंक्ति और स्तंभ के लिए सबसे लंबा बढ़ता पथ वापस करता है।
यदि हमारे पास किसी स्थिति के लिए सबसे लंबे बढ़ते पथ का रिकॉर्ड पहले से है, तो हम बस उसे वापस कर सकते हैं।

आउटपुट

कंसोल में आउटपुट होगा -