DP Optimization(Part-4) | Longest Increasing Subsequence | DP Series(Episode-18)
এই পর্বে আমরা মূলত ডাটা স্ট্রাকচার ব্যাবহারের মাধ্যমে কিছু কিছু ডিপি প্রব্লেমের কমপ্লেক্সিটি কিভাবে কমিয়ে আনা সম্ভব তা দেখবো। Problem: মনে কর, তোমাকে একটি n<=10^4 সাইজের অ্যারে দেয়া আছে। এই অ্যারের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য বের করতে হবে😛 ইংরেজীতে বললে Longest Increasing Subsequence এর Length বের করতে হবে। তাহলে এই প্রব্লেমের সল্যুশন কি হতে পারে? Hints: শেষ থেকে শুরুর দিকে প্রত্যেক পজিশনে দাঁড়িয়ে দেখবো এই পজিশনের ভ্যালুটি অবশ্যই নিলে আমি সর্বোচ্চ কত লেন্থ এর LIS বানাতে পারবো। এভাবে সবগুলো রেজাল্ট এর মধ্যে ম্যাক্সিমাম টা এন্সার। কোডটি হলোঃ এখন, কী হবে যদি n<=10^5 এবং a[i]<=10^5 হয়? উপরের সল্যুশন এ ভালো করে লক্ষ্য করলে দেখবে যে, প্রত্যেক পজিশন i তে দাঁড়িয়ে আমরা দেখি i এর ডানে যেসব ভ্যালু আছে a[i] এর সমান অথবা বড় তাদের মধ্যে কার DP এর ভ্যালু সর্বোচ্চ? যেখানে, dp[i] বলতে বোঝায় ith to nth ইনডেক্সের ভ্যালুগুলো কনসিডার করে সর্বোচ্চ কত লেন্থ এর LIS বানানো যায়। একটু ভালো করে চিন্তা করলে দেখবে ১৫ নম্বর লাইনের ইনার লুপের ক...