DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

3.7.11 · Coding › Algorithm Paradigms

Ek-line goal: Ek array diya gaya hai, usmein sabse lambi subsequence ki length nikalni hai (contiguous nahi!) jiske elements strictly increasing hों.

HUM KYA COMPUTE KAR RAHE HAIN?

Example: A = [10, 9, 2, 5, 3, 7, 101, 18] → LIS = [2, 3, 7, 101] ya [2, 3, 7, 18], length 4.

Approach 1 — DP in $O (n^{2})$

for i in 0..n-1:
    dp[i] = 1
    for j in 0..i-1:
        if A[j] < A[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

Cost: do nested loops → $O (n^{2})$ time, $O (n)$ space.

Worked example Trace

A = [3, 1, 4, 1, 5]

i	A[i]	dp[i]	why
0	3	1	pehle kuch nahi
1	1	1	3 ≮ 1, akela
2	4	2	3 extend karo (dp=1) → 2; 1 extend karo → 2
3	1	1	pehle kuch chhota nahi
4	5	3	4 extend karo (dp=2) → 3

Answer = max = 3 (e.g. [3,4,5]). Yeh step kyu? i=4 par, best predecessor index 2 hai (4, dp 2), isliye dp[4]=3.

Approach 2 — Patience sorting in $O (n lo g n)$

Worked example Trace

A = [10, 9, 2, 5, 3, 7, 101, 18]

x	action	tails after
10	append	`[10]`
9	replace tails[0] (≥9)	`[9]`
2	replace tails[0]	`[2]`
5	append (5>2)	`[2,5]`
3	replace tails[1] (pehla ≥3 hai 5)	`[2,3]`
7	append	`[2,3,7]`
101	append	`[2,3,7,101]`
18	replace tails[3] (pehla ≥18 hai 101)	`[2,3,7,18]`

Length = 4. Yeh step kyu? x=3 par, 3 wahan fit hota hai jahan 5 tha (length-2 tail), use neeche kar deta hai taaki future ke chhote values zyada aasaani se extend ho sakein — isi tarah [2,3,7,18] reachable banta hai.

Figure — DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

Forecast-then-Verify

Recall Answer padhne se pehle:

A=[0,1,0,3,2,3] ke liye LIS length kya hai aur ek aise subsequence ka example? Length 4: [0,1,2,3]. tails se check karo: [0]→[0,1]→ (0 replace karo)[0,1]→[0,1,3]→(3 ko 2 se replace karo)[0,1,2]→[0,1,2,3]. ✓

Flashcards

What is the difference between a subsequence and a subarray?

Subarray contiguous hota hai; subsequence elements ko reorder kiye bina delete karke banta hai (gaps ho sakte hain).

Define the DP state used in the O(n²) LIS solution.

dp[i] = longest increasing subsequence ki length jo exactly index i par end hoti hai.

State the O(n²) LIS recurrence.

dp[i] = 1 + max(0, {dp[j] : j<i and A[j]<A[i]}); answer = max over all dp[i].

Why is the final answer max(dp) and not dp[n-1]?

Kyunki LIS kisi bhi index par end ho sakti hai, zaroor nahi ki last wale par.

In the O(n log n) method, what does tails[k] store?

Length k+1 ki kisi bhi increasing subsequence ki sabse chhoti possible tail value.

Why is the tails array always strictly increasing?

Ek lambi chain ko kaat dene par ek chhoti tail wali chhoti chain milti hai, aur tails[k] woh sabse chhoti tail hai, isliye values length ke saath badhni chahiye.

For each new x in patience sorting, what do you do?

lower_bound se pehla tails[k] >= x dhundho; replace karo, ya x ko append karo agar x saari tails se bada ho.

Why use lower_bound (>=) instead of upper_bound (>) for strict LIS?

Taaki equal values ek fake lambi increasing chain na banayein; >= ise strictly increasing rakhta hai.

Does len(tails) equal the LIS length? Is tails the actual LIS?

len(tails) = sahi LIS length; lekin tails khud ek valid subsequence NAHI hai (ise recover karne ke liye predecessor pointers chahiye).

What are the time complexities of the two LIS methods?

O(n²) DP, aur O(n log n) tails par binary search ke saath.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho cards ko face-up piles mein left se right rakh rahe ho. Rule: ek card sirf us pile par ja sakta hai agar woh us pile ke top card se bada ho, aur tum hamesha use sabse left wali pile par rakhte ho jahan woh fit ho — agar kahin fit nahi hota, toh right mein ek bilkul naya pile shuru karo. Jitne piles bante hain woh cards ki sabse lambi "hamesha barhti hui" line ki length hai jo tum chun sakte ho! Har pile ka top jitna ho sake utna chhota rakha jaata hai taaki baad mein zyada cards stack ho sakein. Woh "leftmost pile" choice hi binary search hai.

Connections

Dynamic Programming — LIS classic 1D DP-on-suffix/prefix pattern hai.
Binary Search — lower_bound O(n log n) speedup deta hai.
Patience Sorting — fast method ke peeche card-pile model.
Longest Common Subsequence (LCS) — LIS(A) = LCS(A, sorted-unique(A)).
Greedy Algorithms — sabse chhoti tails rakhna ek greedy exchange argument hai.
Russian Doll Envelopes — LIS par based ek 2D application.

HUM KYA COMPUTE KAR RAHE HAIN?

Approach 1 — DP in O(n2)

Approach 2 — Patience sorting in O(nlogn)

Forecast-then-Verify

Flashcards

Connections

Concept Map

Approach 1 — DP in $O (n^{2})$

Approach 2 — Patience sorting in $O (n lo g n)$