লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স

১ · সমস্যার সংজ্ঞা

একটি অ্যারে $a[0 \ldots n-1]$ দেওয়া থাকলে, এমন একটি দীর্ঘতম ইনডেক্স-ক্রম $i_1 < i_2 < \cdots < i_k$ খুঁজে বের করতে হবে যেন $a[i_1] < a[i_2] < \cdots < a[i_k]$ (কঠোরভাবে ক্রমবর্ধমান)। আমাদের লক্ষ্য শুধু $k$-এর সর্বোচ্চ মান বের করা। এটি DSA কোর্সে একটি পরিচিত সমস্যা — এখানে আমরা এর $O(n^2)$ DP সমাধানের সঠিকতা প্রমাণ ও বাস্তব যাচাইয়ে মনোযোগ দেব।

২ · DP রিকারেন্স — $O(n^2)$

$dp[i]$ সংজ্ঞায়িত করি এমন LIS-এর দৈর্ঘ্য হিসেবে যা ঠিক ইনডেক্স $i$-তে শেষ হয় (এটাই গুরুত্বপূর্ণ — "প্রথম $i$টি এলিমেন্টের LIS" নয়, বরং "$a[i]$-কে শেষ এলিমেন্ট হিসেবে ব্যবহার করা LIS")।

$$ dp[i] = 1 + \max\big(\{\, dp[j] : 0 \le j < i,\ a[j] < a[i] \,\} \cup \{0\}\big) $$

অর্থাৎ, $a[i]$-এর আগের এমন সব ইনডেক্স $j$ বিবেচনা করা হয় যেখানে $a[j] < a[i]$ (তাই $a[i]$ ঐ সাবসিকোয়েন্সের পরে যোগ করা যায় ক্রম না ভেঙে), এবং সেগুলোর মধ্যে সবচেয়ে লম্বা $dp[j]$-এর সাথে $1$ যোগ করা হয় (নিজেকে গণনা করে)। যদি এমন কোনো $j$ না থাকে (অর্থাৎ $a[i]$-ই সবচেয়ে ছোট বা প্রথম), তাহলে $dp[i] = 1$ ($a[i]$ একাই একটি দৈর্ঘ্য-১ সাবসিকোয়েন্স)। চূড়ান্ত উত্তর $\max_i dp[i]$ (পুরো অ্যারের LIS যেকোনো ইনডেক্সে শেষ হতে পারে)।

অপটিমাল সাবস্ট্রাকচার: যদি $a[i]$-তে শেষ হওয়া একটি অপটিমাল LIS-এর ঠিক আগের এলিমেন্ট $a[j]$ হয় ($j < i$, $a[j] < a[i]$), তাহলে সেই সাবসিকোয়েন্স থেকে $a[i]$ বাদ দিলে যা থাকে সেটি অবশ্যই $a[j]$-তে শেষ হওয়া একটি অপটিমাল LIS হতে হবে — কারণ $a[j]$-তে শেষ হওয়া এর চেয়ে লম্বা কোনো সাবসিকোয়েন্স থাকলে তার শেষে $a[i]$ যোগ করে মূল সমাধানের চেয়ে লম্বা একটি সাবসিকোয়েন্স পাওয়া যেত — যা অপটিমালিটির সাথে সাংঘর্ষিক। আর একই $dp[j]$ মান একাধিক পরবর্তী ইনডেক্স $i$-এর গণনায় পুনরায় ব্যবহৃত হয় — এটাই ওভারল্যাপিং সাবপ্রবলেম।

৩ · যাচাই — নেইভ এক্সপোনেনশিয়াল ব্রুট-ফোর্স বনাম $O(n^2)$ DP

ব্রুট-ফোর্স ভার্সনটি প্রতিটি এলিমেন্টের জন্য "সাবসিকোয়েন্সে রাখা / না রাখা" — এই দুটি সিদ্ধান্ত রিকার্সিভভাবে পরীক্ষা করে (মোট $2^n$ সাবসিকোয়েন্স), শুধু ক্রমবর্ধমান শর্ত বজায় রাখা সিদ্ধান্তগুলোই গ্রহণ করে।

import random

def lis_brute(arr):
    # নেইভ এক্সপোনেনশিয়াল রিকার্সন -- সব 2^n সাবসিকোয়েন্স পরীক্ষা করে
    n = len(arr)
    best = [0]

    def rec(i, prev, length):
        if i == n:
            best[0] = max(best[0], length)
            return
        rec(i + 1, prev, length)              # arr[i] বাদ দেওয়া
        if prev is None or arr[i] > prev:
            rec(i + 1, arr[i], length + 1)    # arr[i] রাখা (শুধু বৈধ হলে)

    rec(0, None, 0)
    return best[0]

def lis_dp(arr):
    # O(n^2) DP -- dp[i] = ইনডেক্স i-তে শেষ হওয়া LIS-এর দৈর্ঘ্য
    n = len(arr)
    if n == 0:
        return 0
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)

rng = random.Random(11)
print(f"{'array':>35} | {'brute':>5} | {'dp (n^2)':>8}")
for trial in range(10):
    n = rng.randint(1, 14)
    arr = [rng.randint(1, 20) for _ in range(n)]
    b = lis_brute(arr)
    d = lis_dp(arr)
    assert b == d, "মিসম্যাচ!"
    print(f"{str(arr):>35} | {b:>5} | {d:>8}")

print("\nসব ১০টি র‍্যান্ডম অ্যারেতে brute-force == DP")

৪ · সংক্ষেপে — $O(n \log n)$ পেশেন্স-সর্টিং পদ্ধতি

$O(n^2)$-এর চেয়ে দ্রুত একটি পদ্ধতি আছে যা tails নামে একটি সহায়ক অ্যারে রাখে — tails[k] হলো এখন পর্যন্ত পাওয়া দৈর্ঘ্য-$(k{+}1)$ ক্রমবর্ধমান সাবসিকোয়েন্সগুলোর মধ্যে সবচেয়ে ছোট সম্ভাব্য শেষ মান। প্রতিটি নতুন এলিমেন্টের জন্য বাইনারি সার্চ (L17-এ কভার করা bisect) দিয়ে সঠিক অবস্থান বের করে tails আপডেট করা হয় — চূড়ান্ত LIS দৈর্ঘ্য হলো tails-এর দৈর্ঘ্য। এই কৌশলের সঠিকতা প্রমাণ এই পাঠের মূল ফোকাসের বাইরে (এটি একটি আলাদা, সূক্ষ্ম ইনভেরিয়েন্ট-ভিত্তিক প্রমাণ দাবি করে), কিন্তু নিচে একটি কার্যকরী কোড স্কেচ দেখানো হলো যা $O(n^2)$ DP-এর সাথে একই টেস্ট কেসগুলোতে মিলিয়ে দেখা হয়েছে:

import bisect

def lis_nlogn(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)

rng2 = random.Random(11)
mismatches = 0
for trial in range(10):
    n = rng2.randint(1, 14)
    arr = [rng2.randint(1, 20) for _ in range(n)]
    if lis_dp(arr) != lis_nlogn(arr):
        mismatches += 1
print("O(n log n) পদ্ধতি O(n^2) DP-এর সাথে মিসম্যাচ পেয়েছে:", mismatches, "বার (১০টির মধ্যে)")