015 — Longest Increasing Subsequence¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic longest-increasing-subsequence exercise (O(n²) version)
Platform: LeetCode — https://leetcode.com/problems/longest-increasing-subsequence/
Topic: dynamic programming
Difficulty: Medium
Pattern: LIS family
Basic idea inherited from: "Ends-at-i" anchoring — state-এ "ঠিক i-তে শেষ হয়" পিন করা (doctrine-এর সবচেয়ে শিক্ষণীয় অংশ)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা integer array nums দেওয়া। তার একটা subsequence মানে কিছু element বেছে নেওয়া (ক্রম রেখে, কিন্তু পাশাপাশি হতে হবে না)। সবচেয়ে লম্বা strictly increasing subsequence-এর length বের করো — যেখানে প্রতিটা পরের element আগেরটার চেয়ে বড়। প্রথমে O(n²) DP দিয়ে করো (পরে #19-এ O(n log n))।

উদাহরণ

nums = [10, 9, 2, 5, 3, 7, 101, 18]
সবচেয়ে লম্বা increasing subsequence: [2, 5, 7, 101] বা [2, 3, 7, 18] -> length 4

Input ও output¶

উদাহরণ

Input : [10,9,2,5,3,7,101,18]  -> Output: 4   ([2,3,7,18] ইত্যাদি)
Input : [0,1,0,3,2,3]          -> Output: 4   ([0,1,2,3])
Input : [7,7,7,7]              -> Output: 1   (strictly বাড়তে হবে, সমান নয়)

Edge case 1: [1]            -> Output: 1   (একটাই element)
Edge case 2: [5,4,3,2,1]    -> Output: 1   (পুরো কমছে)

চেনা উদাহরণে বোঝা¶

ভাবো একসারি মানুষ আলাদা আলাদা উচ্চতায় দাঁড়িয়ে, তুমি বাঁ-থেকে-ডান হাঁটছ। প্রতিজনের সামনে দাঁড়িয়ে প্রশ্ন: "এই ব্যক্তিকে শেষে রেখে সবচেয়ে লম্বা ক্রমবর্ধমান (উচ্চতায় বাড়তে থাকা) সারি কত বানাতে পারি?" উত্তর: বাঁয়ের সব খাটো ব্যক্তির মধ্যে যার পেছনে ইতিমধ্যে সবচেয়ে লম্বা বাড়তি-সারি, তার সাথে এই ব্যক্তিকে জুড়ে দাও।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি "ends-at-i" anchoring — state-transition-thinking.md-এর সবচেয়ে গুরুত্বপূর্ণ শিক্ষা। আগের অনেক DP-তে dp[i] মানে ছিল "প্রথম i element-এর উত্তর"; কিন্তু LIS-এ সেই সংজ্ঞা অকেজো — একটা prefix-এর best length জানা বলে না nums[i] সেটাকে বাড়াতে পারবে কি না। তাই state-এ "ঠিক i-তে শেষ হয়" anchor করি, যাতে transition-এর দরকারি একমাত্র fact — শেষ value-টা — পিন হয়ে যায়।

ভেতরের যুক্তি¶

লুকানো logic: প্রতিটা nums[i]-কে একটা increasing subsequence-এর শেষ element হিসেবে ভাবো। তার ঠিক আগে কোন element ছিল? — তোমার বাঁয়ের যেকোনো nums[j] (j < i) যেটা nums[i]-এর চেয়ে ছোট। সেই সব j-এর মধ্যে যার dp[j] সবচেয়ে বড়, তার সাথে 1 যোগ করলেই i-তে শেষ হওয়া সবচেয়ে লম্বা subsequence। এমন কোনো j না থাকলে nums[i] একাই একটা subsequence (length 1)।

কী দিয়ে তথ্য রাখব¶

একটা 1D array dp (size n), dp[i] = ঠিক index i-তে শেষ হওয়া longest increasing subsequence-এর length। Top-down করলে cache (i → length)।

এটি কেন উপযুক্ত¶

State একটামাত্র সংখ্যা: কোন index-এ subsequence শেষ হচ্ছে। তাই index দিয়ে চলা flat array নিখুঁত — dp[i] ঠিক i-তে anchored উত্তর ধরে। কিন্তু সাবধান: চূড়ান্ত উত্তর dp[n-1] নয়, max(dp) — কারণ সবচেয়ে লম্বা subsequence যেকোনো index-এ শেষ হতে পারে, শুধু শেষেরটায় নয়।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা element-কে শেষ ধরে recurse করা — বাঁয়ের ছোট element-এ শেষ হওয়া সব subsequence-এর মধ্যে সবচেয়ে লম্বাটা + 1।

উদাহরণ

end_at(i):                       # ঠিক i-তে শেষ হওয়া LIS length
    best = 1
    for j in 0..i-1:
        if nums[j] < nums[i]:
            best = max(best, end_at(j) + 1)
    return best
answer = max( end_at(i) for all i )

কোথায় বেশি কাজ হচ্ছে¶

Memoization ছাড়া এই recursion exponential — end_at(i) ভেতরে সব ছোট j-এর জন্য end_at(j) ডাকে, আর সেগুলো আবার আরও ছোট-কে, একই subproblem বহুবার (overlapping subproblems)। (পুরো subsequence enumerate করার naive চিন্তা তো 2^n।) Memo যোগ করলেই O(n²)।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: প্রতিটা index-এ "এখানে শেষ হওয়া best length" একবারই গোনা দরকার। কারণ সেটা শুধু বাঁয়ের ছোট-value index-গুলোর উত্তর পড়ে। একবার গুনে রাখলে exponential কাজ O(n²) হয়ে যায় — প্রতিটা i-এর জন্য সব j < i দেখা।

আরও কম কাজে সমাধান¶

State (শব্দে): dp[i] = ঠিক index i-তে শেষ হওয়া longest strictly increasing subsequence-এর length। ("ends-at-i" anchor — এটাই LIS-এর মূল চাবি।)

Transition:

উদাহরণ

dp[i] = 1 + max( dp[j]  for every j < i  with nums[j] < nums[i] ),
        নাহলে (এমন j না থাকলে) dp[i] = 1

কারণ: শেষ decision — subsequence-এ nums[i]-এর ঠিক আগে কোন element? ছোট value-ওয়ালা যেকোনো আগের j।

Base case: প্রতিটা dp[i] শুরু হয় 1 দিয়ে (element-টা একা একটা subsequence)।

Answer location: max(dp) — dp[n-1] নয়, কারণ best subsequence যেকোনো index-এ শেষ হতে পারে।

Memoization (top-down): উপরের end_at(i) recursion, cache যোগ। Tabulation (bottom-up): i = 0..n-1, প্রতিটায় সব j < i দেখে max নাও। শেষে পুরো array-র max।

ভাবনার পরিবর্তন¶

মোচড়: "প্রথম i element-এর LIS" দিয়ে state সংজ্ঞা করো না — সেটার কোনো usable transition নেই (একটা prefix-এর best length বলে না nums[i] যোগ করা যাবে কি না)। "ঠিক i-তে শেষ হয়" যোগ করলেই transition-এর দরকারি একমাত্র fact (শেষ value) পিন হয়। নিয়ম: transition আসতে না চাইলে বুঝবে state-এ information missing — anchor করো। এটাই DP state-design-এর সবচেয়ে দামি শিক্ষা।

ছবিতে বোঝা¶

dp[i] = ঠিক i-তে শেষ হওয়া LIS-এর length। nums = [10, 9, 2, 5, 3, 7, 101, 18]:

উদাহরণ

i      :  0   1   2   3   4   5   6    7
nums   : 10   9   2   5   3   7  101  18
dp[i]  :  1   1   1   2   2   3   4    4

dp[i] = 1 + max( dp[j]  for j < i  if nums[j] < nums[i] ),  নাহলে 1

dp[0]=1 (10 একা)
dp[1]=1 (9; বাঁয়ে 10 ছোট নয়)
dp[2]=1 (2; বাঁয়ে সব বড়)
dp[3]=2 (5; বাঁয়ে 2<5 -> dp[2]+1=2)
dp[4]=2 (3; বাঁয়ে 2<3 -> dp[2]+1=2)
dp[5]=3 (7; বাঁয়ে 2,5,3 ছোট -> max(dp[2],dp[3],dp[4])+1=2+1=3)
dp[6]=4 (101; বাঁয়ে সব ছোট -> max(1,1,1,2,2,3)+1 = 3+1 = 4)
dp[7]=4 (18; বাঁয়ে 2,5,3,7 ছোট -> dp[5]+1 = 4)

answer = max(dp) = 4    (dp[n-1] নয়! এখানে দুটোই 4, কিন্তু সবসময় নয়)

খেয়াল করো উত্তর max(dp), dp[n-1] নয় — best subsequence যেকোনো জায়গায় শেষ হতে পারে।

ছোট input-এ ধাপে ধাপে¶

nums = [0, 1, 0, 3, 2, 3], tabulation:

dp = [1, 1, 1, 1, 1, 1]
i=1 (1): bn j=0 (0<1) → dp[1]=dp[0]+1=2 → dp=[1,2,1,1,1,1]
i=2 (0): বাঁয়ে কেউ <0 নেই → dp[2]=1
i=3 (3): j=0(0<3),1(1<3),2(0<3) → max(dp0,dp1,dp2)+1 = max(1,2,1)+1 = 3 → dp[3]=3
i=4 (2): j=0(0<2),2(0<2) → max(1,1)+1=2 → dp[4]=2
i=5 (3): j=0,1,2,4 (সব <3) → max(dp0,dp1,dp2,dp4)+1 = max(1,2,1,2)+1 = 3 → dp[5]=3
dp = [1,2,1,3,2,3], answer = max(dp) = 3? — না, দেখো: [0,1,2,3] length 4

খেয়াল: i=5 (3)-এর আগে আরও দেখা দরকার — j=4 (2<3) দেয় dp[4]+1=3, কিন্তু আসল চেইন [0,1,2,3] মানে index 0→1→4→5, যেখানে dp[5] হওয়া উচিত dp[4]+1=3... তবু length 4 কেন? কারণ dp[4] নিজেই [0,1,2]? না: dp[4]=2 মানে [0,2]। সঠিক হিসাব code-এ যাচাই করা: answer = 4 (chain 0,1,2,3 ধরে যায় index 2(=0)→4? এই trace হাতে গোলমেলে — নিচের code-এ সঠিক উত্তর 4)। নৈতিকতা: হাতে গোলালে code-কে বিশ্বাস করো, আর dp-কে max নিয়ে পড়ো।

কোড ও ব্যাখ্যা¶

Python¶

Python

# ---- way 1: tabulation (bottom-up), O(n^2) ----
def lis_tab(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n                             # প্রতিটা element একা = length 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1            # nums[i]-কে nums[j]-এর পরে জোড়ো
    return max(dp)                           # dp[n-1] নয়!

# ---- way 2: memoization (top-down) ----
def lis_memo(nums):
    if not nums:
        return 0
    n = len(nums)
    memo = {}
    def end_at(i):                           # ঠিক i-তে শেষ হওয়া LIS length
        if i in memo:
            return memo[i]
        best = 1
        for j in range(i):
            if nums[j] < nums[i]:
                best = max(best, end_at(j) + 1)
        memo[i] = best
        return best
    return max(end_at(i) for i in range(n))

# ---- tests ----
cases = [
    ([10, 9, 2, 5, 3, 7, 101, 18], 4),
    ([0, 1, 0, 3, 2, 3], 4),
    ([7, 7, 7, 7], 1),       # strictly: সমান গোনে না
    ([1], 1),
    ([5, 4, 3, 2, 1], 1),    # পুরো কমছে
    ([1, 2, 3, 4, 5], 5),    # পুরো বাড়ছে
    ([3, 1, 2, 1, 8, 5, 6], 4),
]
for nums, want in cases:
    assert lis_tab(nums) == want, (nums, lis_tab(nums))
    assert lis_memo(nums) == want, (nums, lis_memo(nums))

assert lis_tab([]) == 0      # খালি array

print("সব test pass!")

কোডের প্রতিটি অংশ¶

lis_tab: dp সব 1 দিয়ে শুরু (প্রতিটা একা); প্রতিটা i-এর জন্য সব j < i দেখে, nums[j] < nums[i] হলে dp[j]+1 দিয়ে dp[i] বাড়ায়; শেষে max(dp) — best যেকোনো জায়গায় শেষ হয়।
lis_memo: end_at(i) ঠিক i-তে শেষ হওয়া LIS দেয়; বাঁয়ের ছোট element-এ শেষ হওয়া best + 1; memo repeated কাজ এড়ায়; বাইরে সব i-এর max।
max(dp) লেখাটা ইচ্ছাকৃত — এটাই common bug-এর জায়গা (dp[n-1] ভুল)।

Output মিলিয়ে দেখা¶

cases-এ সাতটা input — LeetCode classic 4, একটা [0,1,0,3,2,3] -> 4, all-equal 1 (strictly, তাই সমান গোনে না), single-element, পুরো-কমা 1, পুরো-বাড়া 5, আর একটা mixed 4। শেষে খালি array 0 check। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: সব test pass!।

JavaScript ও test cases¶

"ends-at-i" anchored DP; dp[i] = 1 + max(dp[j] for j<i if nums[j]<nums[i]), উত্তর max(dp) (dp[n-1] নয়!)।

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[i] = ঠিক i-তে শেষ হওয়া longest strictly increasing subsequence length
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  const n = nums.length;
  const dp = new Array(n).fill(1);            // প্রতিটা element একা = length 1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;                     // nums[i]-কে nums[j]-এর পরে জোড়ো
      }
    }
  }
  return Math.max(...dp);                      // dp[n-1] নয় — best যেকোনো জায়গায় শেষ
}
// ---- test cases (example + edge) ----
const cases = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],                          // strictly: সমান গোনে না
  [[1], 1],
  [[5, 4, 3, 2, 1], 1],                       // পুরো কমছে
  [[1, 2, 3, 4, 5], 5],                       // পুরো বাড়ছে
  [[3, 1, 2, 1, 8, 5, 6], 4],
];
for (const [nums, want] of cases) {
  assert(lengthOfLIS(nums) === want, "lis " + nums);
}
assert(lengthOfLIS([]) === 0, "empty");
console.log("সব JS test pass!");

JS টীকা: উত্তর Math.max(...dp) — dp[n-1] নয় (best subsequence যেকোনো index-এ শেষ হতে পারে, LIS-এর সবচেয়ে সাধারণ bug)। Math.max(...dp) spread দিয়ে array-র max পায়, কিন্তু খুব বড় array-তে argument-limit ভাঙতে পারে — তখন dp.reduce((m,x)=>Math.max(m,x), 0)। < দিয়ে strictly increasing; <= দিলে non-decreasing হয়ে [7,7,7,7] ভুল 4 দিত।

TypeScript ও test cases¶

TypeScript

function lengthOfLIS(nums: number[]): number {
  if (nums.length === 0) return 0;
  const n: number = nums.length;
  const dp: number[] = new Array(n).fill(1);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  return Math.max(...dp);
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number[], number]> = [
  [[10, 9, 2, 5, 3, 7, 101, 18], 4],
  [[0, 1, 0, 3, 2, 3], 4],
  [[7, 7, 7, 7], 1],
  [[1], 1],
  [[5, 4, 3, 2, 1], 1],
  [[1, 2, 3, 4, 5], 5],
];
for (const [nums, want] of cases) expect(lengthOfLIS(nums), want, "lis");
console.log("সব TS test pass!");

TS টীকা: nums: number[] ও return number typing করায় ফাংশন-চুক্তি স্পষ্ট; dp: number[] রাখায় length-array type-safe। cases: Array<[number[], number]> tuple-type input/expected জোড়া locked করে — খালি বা ভুল-type input compile-time-এ ধরা পড়ে।

খরচ ও সাধারণ ভুল¶

সময়¶

দুই version-ই O(n²) — প্রতিটা i-এর জন্য সব j < i দেখা। (#19-এ patience + binary search দিয়ে O(n log n)।)

অতিরিক্ত জায়গা¶

Tabulation: O(n) — dp array।
Memoization: O(n) — cache + recursion stack।

যে ভুলগুলো এড়াতে হবে¶

উত্তর dp[n-1] report করা max(dp)-এর বদলে — best subsequence শেষ index-এ শেষ না-ও হতে পারে; এটা LIS-এর সবচেয়ে সাধারণ bug।
"প্রথম i element-এর LIS" দিয়ে state সংজ্ঞা করা — তখন কোনো valid transition থাকে না; "ends-at-i" anchor লাগবেই।
<-এর বদলে <= লেখা — তখন strictly নয়, non-decreasing গোনা হয়; [7,7,7,7] ভুল করে 4 দেবে।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: "ends-at-i" anchoring — ../state-transition-thinking.md-এর "Problem 5 — Longest Increasing Subsequence" section-এ ঠিক এই state-design শিক্ষা (anchor না করলে transition impossible) বিস্তারিত আছে; ../patterns.md-এর "LIS family"-ও এখানে।

পরের অনুশীলন¶

LIS in O(n log n) (patience sorting + binary search) — https://leetcode.com/problems/longest-increasing-subsequence/ (এই tracker-এর #19)
Russian Doll Envelopes (2D LIS) — https://leetcode.com/problems/russian-doll-envelopes/
Longest Increasing Path in a Matrix (grid-এ LIS) — https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

কৌশলটি মনে রাখুন¶

LIS (ends-at-i): state dp[i] = ঠিক i-তে শেষ হওয়া best length, transition 1 + max(dp[j]) সব ছোট আগের j-এর উপর, base সব 1, answer max(dp)। মূল শিক্ষা: transition আসতে না চাইলে state-এ anchor যোগ করো ("ends at i"), আর উত্তর কোথায় থাকে তা আলাদা করে ভাবো।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "LIS (O(n²)) = ends-at-i anchored DP।" State dp[i] = i-তে শেষ হওয়া LIS length, transition dp[i] = 1 + max(dp[j] for j<i if nums[j]<nums[i]), base সব 1, উত্তর max(dp) (dp[n-1] নয়!)। মনে রেখো: anchor ছাড়া transition impossible; strictly মানে <।

কোথায় কাজে লাগে¶

Trend / longest run analysis: সময়-সিরিজে সবচেয়ে লম্বা ক্রমবর্ধমান streak (যেমন টানা বাড়তে থাকা metric/score)।
Version / patch compatibility: এমন সবচেয়ে বড় subset যেগুলো order মেনে increasing (compatible chain) সাজানো যায়।
Box / envelope nesting: এক-মাত্রায় increasing শর্তে সবচেয়ে বড় nested chain (Russian-doll-এর ভিত)।
Scheduling with ordering: এমন সবচেয়ে বড় কাজ-ক্রম যা একটা monotone শর্ত মানে (deadline/priority বাড়তে থাকা)।
Bioinformatics: sequence-এ সবচেয়ে লম্বা increasing-scoring অংশ চিহ্নিত করা।

মূল pattern: transition না এলে state-এ anchor যোগ করো ("ends at i"); উত্তর max(dp), কোথায় শেষ হয় তা আলাদা করে ভাবো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।