ক্রমবর্ধমান
সংখ্যার একটি ক্রম যাতে প্রতিটি পরবর্তী উপাদান পূর্ববর্তী উপাদানের থেকে বড় বা সমান হয় একটি ক্রমবর্ধমান ক্রম।
উদাহরণস্বরূপ,
4, 6, 8, 9, 11, 14 is increasing sequence 3, 3, 3, 3, 3, 3, 3 is also an increasing sequence
সমস্যা:
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা 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
