বর্ধমান ক্রম
একটি সংখ্যা সিকোয়েন্স যেখানে প্রতিটি পরবর্তী এলিমেন্ট পূর্ববর্তী এলিমেন্ট থেকে বড় বা সমান, তাকে বর্ধমান ক্রম বলা হয়।
উদাহরণস্বরূপ,
4, 6, 8, 9, 11, 14 হল বর্ধমান ক্রম 3, 3, 3, 3, 3, 3, 3 ও বর্ধমান ক্রম
সমস্যা:
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ২ডি সংখ্যা অ্যারে (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= 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কোড ব্যাখ্যা:
ব্যাঙ্কট্র্যাকিং ডেপথ-ফার্স্ট সার্চ ব্যবহার করা হয়েছে। রিকার্শন ফাংশনটি একটি দেয়া রো ও কলামের জন্য সবচেয়ে দীর্ঘ বর্ধমান পথ রিটার্ন করে। যদি ইতিমধ্যে কোনো পজিশনের জন্য রেকর্ড থাকে, তবে সেটি সরাসরি রিটার্ন করা হয়।
আউটপুট
কনসোলে আউটপুট হবে –
4
