015 — Longest Increasing Subsequence¶

Source¶

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-এর সবচেয়ে শিক্ষণীয় অংশ)

1. Problem in simple words¶

একটা 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

2. Which basic idea does this inherit from?¶

ভিত্তি "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-টা — পিন হয়ে যায়।

3. What is the hidden math or logic?¶

লুকানো 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)।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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 = 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 যেকোনো জায়গায় শেষ হতে পারে।

8. Example input and 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   (পুরো কমছে)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা 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 )

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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।

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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 নিয়ে পড়ো।

15. Python solution¶

# ---- 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!")

16. Line-by-line code explanation¶

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] ভুল)।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

উত্তর 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 দেবে।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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"), আর উত্তর কোথায় থাকে তা আলাদা করে ভাবো।

24. Final summary¶

ভবিষ্যতের আমাকে: "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 মানে <।

25. JavaScript solution (with 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] নয়!)।

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 দিত।

26. TypeScript solution (with test cases)¶

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-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)¶

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।