ডায়নামিক প্রোগ্রামিং৮ মিনিট পড়া

লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স বা দীর্ঘতম ক্রমবর্ধমান উপক্রম (Longest Increasing Subsequence)

একটি এলোমেলো অনুক্রমের বা সিকোয়েন্সের ভেতর লুকিয়ে থাকা দীর্ঘতম সিঁড়িটিকে খুঁজে বের করুন
O(n²) DP:সহজ এবং সঠিক বা নির্ভুল (Simple and correct)O(n log n):পেশেন্স সর্টিং ট্রিক বা ধৈর্যশীল বাছাইয়ের কৌশল (Patience sorting trick)space:\(O(n)\)

কয়েকটি এলোমেলো বা র‍্যান্ডম (random) সংখ্যার একটি সিকোয়েন্স বা অনুক্রমের কথা কল্পনা করুন: 3, 1, 4, 1, 5, 9, 2, 6। এর ভেতরে লুকিয়ে আছে একটি "সিঁড়ি (staircase)" — অর্থাৎ সংখ্যাগুলোর এমন একটি চেইন বা শিকল যেখানে প্রতিটি সংখ্যা তার ঠিক আগের সংখ্যাটির চেয়ে অবশ্যই বড় হতে হবে। আপনি চাইলে মাঝখানের কিছু সংখ্যাকে এড়িয়ে যেতে বা স্কিপ (skip) করতে পারবেন, কিন্তু আপনি কোনোভাবেই তাদের একে অপরের ক্রম বা রিঅর্ডার (reorder) পরিবর্তন করতে পারবেন না। এখানকার এমন দীর্ঘতম সিঁড়িটি হলো [1, 4, 5, 9] অথবা [1, 4, 5, 6] — যাদের উভয়েরই দৈর্ঘ্য (length) হলো 4।

আর এটিই হলো লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স বা দীর্ঘতম ক্রমবর্ধমান উপক্রম (Longest Increasing Subsequence — LIS)। এটি মূলত বিভিন্ন শিডিউলিং (scheduling) সমস্যায়, অ্যালগরিদমের জটিলতা বিশ্লেষণের সময়, এমনকি বিভিন্ন তাসের বা কার্ড গেমের (card games) সময়ও সামনে এসে থাকে।

\(O(n^2)\) ডিপি-র পদ্ধতি বা অ্যাপ্রোচ (The \(O(n^2)\) DP Approach)

ধরি dp[i] = আপনার দীর্ঘতম ক্রমবর্ধমান উপক্রমের দৈর্ঘ্য যা i সূচকে বা ইনডেক্সে (index) গিয়ে শেষ হয়। প্রতিটি \(i\) এর জন্য, এর পেছনের দিকে থাকা এমন প্রতিটি \(j < i\) এর দিকে লক্ষ্য করুন যেখানে A[j] < A[i] হবে: dp[i] = max(dp[j] + 1)। এর বেস কেস (Base case): dp[i] = 1 (কারণ প্রতিটি সিঙ্গেল বা একক ইলিমেন্ট (element) নিজে নিজেই 1 দৈর্ঘ্যের একটি সাবসিকোয়েন্স)। উত্তরটি হবে মূলত সমস্ত dp[i] মানগুলোর মধ্যে সবচেয়ে বড় বা ম্যাক্সিমাম (maximum) মানটি।

এতে মূলত \(O(n^2)\) টাইম বা সময় লাগে — এটি n ≤ 10,000 এর জন্য বেশ ভালোভাবেই কাজ করবে, তবে n = 100,000 এর জন্য এটি খুব ধীরগতির হয়ে যাবে।

\(O(n \log n)\) পেশেন্স সর্টিং ট্রিক বা কৌশল (The \(O(n \log n)\) Patience Sorting Trick)

তাস খেলার বা কার্ড গেমের (card game) কথা কল্পনা করুন (যাকে আমরা পেশেন্স গেম বা ধৈর্য্যের খেলাও বলি): আপনি কার্ডগুলোকে বিভিন্ন স্তূপে বা পাইলে (piles) সাজিয়ে রাখছেন, এবং প্রতিটি নতুন কার্ডকে সবথেকে বাম দিকের (leftmost) এমন একটি স্তূপের উপর রাখতে হবে যে স্তূপের উপরের কার্ডটি মূলত আপনার বসা নতুন কার্ডটির চেয়ে সমান অথবা বড় (greater than or equal to) হবে। আর যদি এরকম কোনো স্তূপ বা পাইল খুঁজে না পান, তবে একটি সম্পূর্ণ নতুন পাইল তৈরি বা শুরু করুন। একেবারে শেষে গিয়ে আপনার থাকা ওই মোট স্তূপ বা পাইলের সংখ্যাই হলো আপনার LIS-এর দৈর্ঘ্যের সমান।

কোডের (code) ক্ষেত্রে, একটি টেইলস অ্যারে (tails array) মেইনটেইন করুন বা পরিচালনা করুন, যেখানে tails[k] হবে মূলত এখন পর্যন্ত পাওয়া k+1 দৈর্ঘ্যের ক্রমবর্ধমান সমস্ত সাবসিকোয়েন্সগুলোর মধ্যে সম্ভবপর সবচেয়ে ছোট বা স্মলেস্ট (smallest) টেইল ইলিমেন্ট (tail element)। প্রতিটি x ইলিমেন্টের জন্য:

যদি x > tails.last হয় — তাহলে x-কে এর শেষে যুক্ত করুন (অর্থাৎ আপনার LIS-এর দৈর্ঘ্য আরও এক ধাপ বেড়ে গেছে)।

অন্যথায় — tails[pos] ≥ x এই শর্তটি মেনে সবচেয়ে বাম দিকের (leftmost) অবস্থানটি খুঁজতে একটি বাইনারি সার্চ (binary search) প্রয়োগ করুন, এবং তারপর সেই ইলিমেন্টটিকে x দ্বারা পুনস্থাপিত বা রিপ্লেস (replace) করুন।

আপনার এই টেইলস অ্যারেটি (tails array) সবসময়েই সর্টেড বা সাজানো অবস্থায় (sorted) থাকে (এটি এমন একটি অপরিবর্তনীয় সত্য বা ইনভ্যারিয়েন্ট (invariant) যা আপনি চাইলেই প্রমাণ করতে পারবেন), তাই বাইনারি সার্চের (binary search) কারণে এখানকার প্রতিটি পদক্ষেপে মূলত \(O(\log n)\) সময় লাগে — যা আপনাকে সর্বমোট \(O(n \log n)\) রানটাইম প্রদান করে।

রিপ্লেস করা বা প্রতিস্থাপন করা কেন কাজ করে (Why Replacing Works)

tails[pos]-কে এর থেকে ছোট কোনো মান x দিয়ে রিপ্লেস বা প্রতিস্থাপন করা হলে তা বিদ্যমান কোনো সাবসিকোয়েন্সকেই ভেঙে ফেলে না — বরং এটি ভবিষ্যতে আরও বড় সাবসিকোয়েন্স পাওয়ার সম্ভাবনা ও দোরগোড়া খুলে দেয়। একটি অপেক্ষাকৃত ছোট লেজ বা টেইল (tail) মূলত ভবিষ্যতের এক্সটেনশন বা প্রসারণের জন্য সবসময়ই ভালো: কারণ এর ফলে আপনার অ্যারের ভেতরে থাকা আরও অনেক বেশি সংখ্যক ইলিমেন্ট এটিকে সহজে অনুসরণ (follow) করতে সক্ষম হবে।

দ্রষ্টব্য: এই টেইলস অ্যারেটি (tails array) মূলত নিজে থেকে কোনো সত্যিকারের বা অ্যাকচুয়াল (actual) সাবসিকোয়েন্সকে রিপ্রেজেন্ট করে না বা বোঝায় না — এটি নিছকই একটি হিসাব রাখার বা বুককিপিং (bookkeeping) করার কাঠামো বা স্ট্রাকচার। এর একেবারে শেষে থাকা tails-এর দৈর্ঘ্য বা সাইজটিই হলো LIS-এর দৈর্ঘ্য, তবে এই tails-এর মধ্যে থাকা ইলিমেন্টগুলো হয়তো আসল বা মূল LIS-টি গঠন নিন করতে পারে।

LIS — \(O(n \log n)\) পেশেন্স সর্টিং (patience sorting)

import bisect


def lis(arr):
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)


print(lis([3, 1, 4, 1, 5, 9, 2, 6]))  # 4
print(lis([2, 5, 3, 7, 4, 8, 6]))     # 4
Output
4
4

Complexity

🐢 \(O(n^2)\) ডিপি (DP)
প্রতিটি \(i\) এর জন্য, এর পেছনের থাকা সমস্ত \(j < i\) কে চেক বা যাচাই করুন — এটি বেশ সহজ এবং প্রয়োগ করান বেশ সোজা (easy to implement), এবং n ≤ 10,000 এর জন্য বেশ ভালোভাবেই কাজ করে
অল-পেয়ার্স চেক বা সব জোড়া যাচাই (All-pairs check) \(O(n^2)\)
⚡ \(O(n \log n)\) পেশেন্স সর্টিং (patience sorting)
সর্বদা-সর্টেড বা সাজানো অবস্থায় থাকা টেইলস অ্যারেটির (tails array) প্রতিটি উপাদানের জন্য একটি করে বাইনারি সার্চ (binary search) প্রয়োগ করা হয়
উপাদান বা ইলিমেন্ট প্রতি বাইনারি সার্চ (Binary search per element) \(O(n \log n)\)
📦 জায়গা বা স্পেস (Space)
n সাইজ বা আকারের dp অ্যারে অথবা tails অ্যারে; মূল রিকনস্ট্রাকশন বা পুনর্নির্মাণের জন্য এর সাথে একটি \(O(n)\) পূর্বসূরি বা প্রেডিসেসর অ্যারে (predecessor array) যুক্ত করুন
লিনিয়ার স্টোরেজ বা জায়গা (Linear storage) \(O(n)\)
🔍 রিকনস্ট্রাকশন বা পুনর্নির্মাণ (Reconstruction)
এই \(O(n^2)\) ডিপি-র (DP) সময় এর প্রেডিসেসর বা পূর্বসূরিগুলোকে ট্র্যাক (Track) করে রাখুন; এদের \(O(n \log n)\) সংস্করণের ক্ষেত্রে অতিরিক্ত যত্ন বা কেস হ্যান্ডেলিংয়ের প্রয়োজন হয়
\(O(n)\) অতিরিক্ত ট্র্যাকিং (extra tracking) \(O(n)\)

ছোট কুইজ

এই [2, 5, 3, 7, 4, 8, 6] অ্যারেটির বা তালিকার LIS-এর সাইজ বা দৈর্ঘ্য কত হবে?

পড়া চালিয়ে যান

লংগেস্ট কমন সাবসিকোয়েন্স বা দীর্ঘতম সাধারণ উপক্রম (Longest Common Subsequence)
দুটি সিকোয়েন্সের বা অনুক্রমের মধ্যে থাকা দীর্ঘতম একই অংশ বা গল্পটি খুঁজে বের করুন — যেখানে মাঝখানের কিছু অংশ এড়িয়ে যাওয়া বা স্কিপ (skip) করা সম্ভব
→
ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→