बढ़ते क्रम
संख्याओं का एक क्रम जिसमें प्रत्येक अनुवर्ती तत्व या तो पिछले तत्व से बड़ा या बराबर होता है, एक बढ़ता हुआ क्रम होता है।
उदाहरण के लिए,
4, 6, 8, 9, 11, 14 is increasing sequence 3, 3, 3, 3, 3, 3, 3 is also an increasing sequence
समस्या:
हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना आवश्यक है जो संख्याओं की 2-डी सरणी लेता है, एआर, एकमात्र तर्क के रूप में। हमारे फ़ंक्शन को उस सरणी में उस सबसे लंबे पथ की लंबाई को खोजना और वापस करना चाहिए जिसमें केवल बढ़ती संख्याएं हों।
उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -
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