Longest Increasing Subsequence (LIS)
What Is LIS?
A subsequence is elements in original order (not necessarily contiguous). An increasing subsequence has each element strictly greater than the previous.
nums = [10, 9, 2, 5, 3, 7, 101, 18] Some increasing subsequences: [2, 3, 7, 101] length 4 [2, 5, 7, 18] length 4 [2, 3, 7, 18] length 4 LIS length = 4 (multiple valid LIS exist) NOT a valid increasing subsequence: [9, 2, 5] — 9 > 2: not strictly increasing [5, 3, 7] — 5 > 3: not strictly increasing KEY: "Ending at index i" thinking is central to the O(n²) DP.
Approach 1: O(n²) DP
STATE: dp[i] = length of LIS ending EXACTLY at index i
RECUR: dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]
(extend the best LIS ending at any earlier smaller element)
If no such j exists: dp[i] = 1 (just the element itself)
BASE: dp[i] = 1 for all i (single element is LIS of length 1)
ANSWER: max(dp[0], dp[1], ..., dp[n-1])
NOTE: Unlike grid DP where answer is dp[n], here the LIS might END
anywhere — take the MAX over all dp[i].
TRACE for nums = [3, 1, 8, 2, 5]:
dp[0]: nums[0]=3, no j<0 → dp[0]=1
dp[1]: nums[1]=1, no j where nums[j]<1 → dp[1]=1
dp[2]: nums[2]=8
j=0: nums[0]=3<8 → dp[0]+1=2
j=1: nums[1]=1<8 → dp[1]+1=2
dp[2]=2
dp[3]: nums[3]=2
j=0: nums[0]=3>2 → skip
j=1: nums[1]=1<2 → dp[1]+1=2
dp[3]=2
dp[4]: nums[4]=5
j=0: nums[0]=3<5 → dp[0]+1=2
j=1: nums[1]=1<5 → dp[1]+1=2
j=2: nums[2]=8>5 → skip
j=3: nums[3]=2<5 → dp[3]+1=3
dp[4]=3
dp = [1, 1, 2, 2, 3]
LIS = max(dp) = 3 ← [1,2,5] or [3,5]... wait [1,2,5] ✓
WHY MAX OVER ALL dp[i]?
dp[i] = "ending at i" — the LIS doesn't have to end at the last element.
In nums=[5,4,3,2,1], dp=[1,1,1,1,1], LIS=1 (decreasing array).
If we only returned dp[n-1] we'd miss when the LIS ends early.
Approach 2: O(n log n) — Patience Sorting
The key insight: maintain a tails array where tails[k] = smallest possible tail of any increasing subsequence of length k+1.
ALGORITHM:
tails = [] ← empty initially
For each num in nums:
Use binary search to find position pos where tails[pos] >= num
If pos == len(tails): append num ← extends longest subsequence
Else: replace tails[pos] with num ← smaller tail = better
LIS length = len(tails)
WHY tails IS ALWAYS SORTED:
We only append to the end (larger than all) or replace an element
with something smaller in the same slot — never violating sorted order.
WHY REPLACE IS CORRECT:
tails[pos] >= num. Replacing with num gives a smaller tail at position pos.
This doesn't change the LIS LENGTH — just makes future extensions more likely.
Example: tails=[1,3] → process 2 → tails=[1,2]. LIS length still 2.
But now future element 3 can extend to length 3: [1,2,3] vs [1,3] stuck.
TRACE for nums = [3, 1, 8, 2, 5]:
num=3: tails=[] → binary search: pos=0=len(tails) → append → tails=[3]
num=1: tails=[3] → binary search for 1: pos=0 (tails[0]=3>=1) → replace → tails=[1]
num=8: tails=[1] → binary search for 8: pos=1=len(tails) → append → tails=[1,8]
num=2: tails=[1,8] → binary search for 2: pos=1 (tails[1]=8>=2) → replace → tails=[1,2]
num=5: tails=[1,2] → binary search for 5: pos=2=len(tails) → append → tails=[1,2,5]
LIS length = len(tails) = 3 ✓
TRACE for nums = [10, 9, 2, 5, 3, 7, 101, 18]:
10 → [10]
9 → [9] (replace 10 at pos 0)
2 → [2] (replace 9 at pos 0)
5 → [2,5] (append)
3 → [2,3] (replace 5 at pos 1)
7 → [2,3,7] (append)
101 → [2,3,7,101] (append)
18 → [2,3,7,18] (replace 101 at pos 3)
LIS length = 4 ✓ actual LIS: [2,3,7,18] or [2,5,7,18] etc.
IMPORTANT: tails is NOT necessarily the actual LIS.
In the second trace, tails=[2,3,7,18] happens to be a valid LIS.
But in general tails can mix elements from different subsequences.
To PRINT the actual LIS, use the index-tracking technique below.
Printing the Actual LIS
TECHNIQUE: Track a parent[] array alongside dp[].
For each dp[i], record the index j that gave dp[i] its max value.
Then backtrack from the index of max(dp) using parent[].
TRACE for nums = [3, 1, 8, 2, 5]:
dp = [1, 1, 2, 2, 3]
parent = [-1,-1, 0, 1, 3] (parent[i] = j that maximized dp[i])
Parent explanations:
dp[2]=2 came from dp[0] (j=0, nums[0]=3<8) → parent[2]=0
dp[3]=2 came from dp[1] (j=1, nums[1]=1<2) → parent[3]=1
dp[4]=3 came from dp[3] (j=3, nums[3]=2<5) → parent[4]=3
Max dp[i] = dp[4]=3 at index 4.
Backtrack: 4 → parent[4]=3 → parent[3]=1 → parent[1]=-1 (stop)
Indices visited: [4, 3, 1] → reversed: [1, 3, 4]
nums at these indices: nums[1]=1, nums[3]=2, nums[4]=5 → LIS = [1, 2, 5] ✓
Complete Implementations
1import java.util.*;
2
3public class LIS {
4
5 // ── O(n²) DP: LIS length ─────────────────────────────────────────
6 public static int lisDP(int[] nums) {
7 int n = nums.length;
8 int[] dp = new int[n];
9 Arrays.fill(dp, 1); // Every element is LIS of length 1
10
11 for (int i=1; i<n; i++) {
12 for (int j=0; j<i; j++) {
13 if (nums[j] < nums[i]) {
14 dp[i] = Math.max(dp[i], dp[j] + 1);
15 }
16 }
17 }
18
19 return Arrays.stream(dp).max().getAsInt();
20 }
21
22 // ── O(n²) DP: print actual LIS ───────────────────────────────────
23 public static List<Integer> printLIS(int[] nums) {
24 int n = nums.length;
25 int[] dp = new int[n];
26 int[] parent = new int[n];
27 Arrays.fill(dp, 1);
28 Arrays.fill(parent, -1);
29
30 int maxLen = 1, maxIdx = 0;
31
32 for (int i=1; i<n; i++) {
33 for (int j=0; j<i; j++) {
34 if (nums[j] < nums[i] && dp[j]+1 > dp[i]) {
35 dp[i] = dp[j] + 1;
36 parent[i] = j; // Record where max came from
37 }
38 }
39 if (dp[i] > maxLen) { maxLen = dp[i]; maxIdx = i; }
40 }
41
42 // Backtrack using parent[]
43 List<Integer> lis = new ArrayList<>();
44 for (int idx=maxIdx; idx!=-1; idx=parent[idx]) {
45 lis.add(0, nums[idx]); // Prepend for correct order
46 }
47 return lis;
48 }
49
50 // ── O(n log n): LIS length using binary search ───────────────────
51 public static int lisNLogN(int[] nums) {
52 List<Integer> tails = new ArrayList<>();
53
54 for (int num : nums) {
55 // Binary search: find first index where tails[pos] >= num
56 int lo=0, hi=tails.size();
57 while (lo < hi) {
58 int mid = (lo+hi)/2;
59 if (tails.get(mid) < num) lo = mid+1;
60 else hi = mid;
61 }
62 if (lo == tails.size()) tails.add(num); // Extend
63 else tails.set(lo, num); // Replace
64 }
65
66 return tails.size();
67 }
68
69 // ── O(n log n): using Java's Arrays.binarySearch ─────────────────
70 public static int lisNLogNClean(int[] nums) {
71 int[] tails = new int[nums.length];
72 int len = 0;
73
74 for (int num : nums) {
75 int pos = Arrays.binarySearch(tails, 0, len, num);
76 if (pos < 0) pos = -(pos+1); // Convert to insertion point
77 tails[pos] = num;
78 if (pos == len) len++; // Extended LIS
79 }
80
81 return len;
82 }
83
84 // ── Number of LIS ─────────────────────────────────────────────────
85 public static int numberOfLIS(int[] nums) {
86 int n = nums.length;
87 int[] dp = new int[n]; // Length of LIS ending at i
88 int[] cnt = new int[n]; // Count of LIS of that length ending at i
89 Arrays.fill(dp, 1);
90 Arrays.fill(cnt, 1);
91
92 int maxLen = 1;
93 for (int i=1; i<n; i++) {
94 for (int j=0; j<i; j++) {
95 if (nums[j] < nums[i]) {
96 if (dp[j]+1 > dp[i]) {
97 dp[i] = dp[j]+1; // Found longer LIS ending at i
98 cnt[i] = cnt[j]; // Reset count to j's count
99 } else if (dp[j]+1 == dp[i]) {
100 cnt[i] += cnt[j]; // Same length — add j's count
101 }
102 }
103 }
104 maxLen = Math.max(maxLen, dp[i]);
105 }
106
107 // Sum counts of all indices where dp[i] == maxLen
108 int total = 0;
109 for (int i=0; i<n; i++) if (dp[i] == maxLen) total += cnt[i];
110 return total;
111 }
112
113 // ── Longest Bitonic Subsequence ───────────────────────────────────
114 public static int longestBitonic(int[] nums) {
115 int n = nums.length;
116 int[] lis = new int[n]; // LIS ending at i (left side of peak)
117 int[] lds = new int[n]; // LDS starting at i (right side of peak)
118 Arrays.fill(lis, 1); Arrays.fill(lds, 1);
119
120 // LIS from left
121 for (int i=1; i<n; i++)
122 for (int j=0; j<i; j++)
123 if (nums[j] < nums[i]) lis[i] = Math.max(lis[i], lis[j]+1);
124
125 // LDS from right (= LIS from right traversal)
126 for (int i=n-2; i>=0; i--)
127 for (int j=n-1; j>i; j--)
128 if (nums[j] < nums[i]) lds[i] = Math.max(lds[i], lds[j]+1);
129
130 int max = 0;
131 for (int i=0; i<n; i++) max = Math.max(max, lis[i]+lds[i]-1);
132 return max;
133 }
134
135 // ── Russian Doll Envelopes ────────────────────────────────────────
136 // Sort: ascending width, DESCENDING height when widths equal
137 // Then LIS on heights
138 public static int maxEnvelopes(int[][] envelopes) {
139 Arrays.sort(envelopes, (a,b) ->
140 a[0] != b[0] ? a[0]-b[0] : b[1]-a[1]); // w asc, h desc on tie
141
142 // LIS on heights using O(n log n)
143 int[] tails = new int[envelopes.length];
144 int len = 0;
145 for (int[] env : envelopes) {
146 int h = env[1];
147 int pos = Arrays.binarySearch(tails, 0, len, h);
148 if (pos < 0) pos = -(pos+1);
149 tails[pos] = h;
150 if (pos == len) len++;
151 }
152 return len;
153 }
154
155 public static void main(String[] args) {
156 int[] a = {10,9,2,5,3,7,101,18};
157 int[] b = {3,1,8,2,5};
158
159 System.out.println("LIS O(n²) a: " + lisDP(a)); // 4
160 System.out.println("LIS O(n log n) a: " + lisNLogN(a)); // 4
161 System.out.println("Print LIS b: " + printLIS(b)); // [1,2,5]
162 System.out.println("Number of LIS: " +
163 numberOfLIS(new int[]{1,3,5,4,7})); // 2
164 System.out.println("Longest Bitonic: " +
165 longestBitonic(new int[]{1,11,2,10,4,5,2,1})); // 6
166 int[][] env = {{5,4},{6,4},{6,7},{2,3}};
167 System.out.println("Russian Doll: " + maxEnvelopes(env)); // 3
168 }
169}Output:
LIS O(n²) a: 4
LIS O(n log n) a: 4
Print LIS b: [1, 2, 5]
Number of LIS: 2
Longest Bitonic: 6
Russian Doll: 3
tails Is NOT the Actual LIS
CRITICAL MISCONCEPTION: The tails array gives the CORRECT LENGTH but NOT necessarily the actual LIS. EXAMPLE: nums = [3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12] Processing step by step: 3 → [3] 5 → [3,5] 6 → [3,5,6] 2 → [2,5,6] ← 2 replaced 3 5 → [2,5,6] ← 5 replaced 5 (no change) 4 → [2,4,6] ← 4 replaced 5 19 → [2,4,6,19] 5 → [2,4,5,19] ← 5 replaced 6 6 → [2,4,5,6] ← 6 replaced 19 7 → [2,4,5,6,7] 12 → [2,4,5,6,7,12] tails = [2,4,5,6,7,12] — length 6 is CORRECT. But [2,4,5,6,7,12] is indeed a valid LIS here. Counter-example where tails is NOT an actual LIS: nums = [1,7,8,4,5,6] 1→[1], 7→[1,7], 8→[1,7,8], 4→[1,4,8], 5→[1,4,5], 6→[1,4,5,6] tails=[1,4,5,6] — length 4 ✓ But is [1,4,5,6] an actual LIS of [1,7,8,4,5,6]? 1 at index 0, 4 at index 3, 5 at index 4, 6 at index 5 → YES, it is! ✓ Trickier: nums = [2,6,8,3,4,5,1] 2→[2], 6→[2,6], 8→[2,6,8], 3→[2,3,8], 4→[2,3,4], 5→[2,3,4,5], 1→[1,3,4,5] tails=[1,3,4,5] — length 4 ✓ Is [1,3,4,5] the actual LIS? 1 is at index 6, but 3 is at index 3 (before 1!) [1,3,4,5] is NOT a valid LIS of the original array! Actual LIS: [2,3,4,5] or [2,6,8] → wait, [2,3,4,5] at indices 0,3,4,5 ✓ TO PRINT the actual LIS with O(n log n): use the index-tracking technique (requires tracking predecessor indices during the patience sort process). For interviews: use O(n²) DP with parent[] — simpler to implement correctly.
LIS Family Problems Summary
VARIANT DESCRIPTION APPROACH ──────────────────────────────────────────────────────────────────────────── LIS (strict increasing) Strictly increasing subsequence O(n²) DP or O(n log n) LNdS (non-decreasing) Allow equal elements Replace < with <= Longest Decreasing Subseq. Strictly decreasing LIS on reversed/negated array Number of LIS Count all LIS of max length dp[]+cnt[] arrays Longest Bitonic Subseq. Increase then decrease LIS from left + LDS from right Russian Doll Envelopes 2D LIS with (w,h) pairs Sort + 1D LIS on heights Box Stacking 3D LIS variant Sort by area; LIS on height REDUCE TO LIS: Non-decreasing: change nums[j] < nums[i] to nums[j] <= nums[i] Decreasing: negate all elements or reverse array, then find LIS Longest Bitonic: lis[i] + lds[i] - 1, take max over all i Russian Doll: sort by (w asc, h desc on ties), LIS on heights only
Complexity Summary
| Approach | Time | Space | Notes |
|---|---|---|---|
| O(n²) DP (length) | O(n²) | O(n) | Simple; handles all variations |
| O(n²) DP (print) | O(n²) | O(n) | parent[] array for backtrack |
| O(n log n) patience | O(n log n) | O(n) | tails + binary search |
| Number of LIS | O(n²) | O(n) | dp[] + cnt[] |
| Longest Bitonic | O(n²) | O(n) | Two LIS passes |
| Russian Doll | O(n log n) | O(n) | Sort + LIS on heights |
Common Mistakes
Taking dp[n-1] instead of max(dp). Unlike grid DP where the answer is at the last cell, LIS might end anywhere in the array. A decreasing array has every dp[i]=1, but dp[n-1]=1 is the correct answer — always take max(dp). Taking just dp[n-1] gives wrong answers when the LIS ends before the last element.
Confusing tails with the actual LIS. The tails array in O(n log n) gives the correct LENGTH but is not always a valid LIS of the input. Use O(n²) DP with parent[] backtracking if you need to print the actual subsequence. Claiming "tails is the LIS" is a frequent incorrect interview answer.
Number of LIS: resetting cnt[i] when dp[i] improves, not adding. When dp[j]+1 > dp[i] (found a strictly longer LIS ending at i via j), set dp[i]=dp[j]+1 and RESET cnt[i]=cnt[j]. Don't add — the previous shorter LIS count is irrelevant now. When dp[j]+1 == dp[i] (same length), ADD cnt[j] to cnt[i].
Longest Bitonic: not subtracting 1. lis[i]+lds[i] counts nums[i] twice (as the last element of increasing part AND first element of decreasing part). Subtracting 1 gives the correct bitonic length. Also: bitonic requires BOTH parts to be non-empty of length ≥ 1, so a strictly increasing or decreasing array still has a valid bitonic subsequence (one side is just the single peak).
Russian Doll: sorting same-width envelopes by height ascending instead of descending. With ascending height sort for equal widths, the LIS algorithm might pick two same-width envelopes (their heights are increasing). Descending height for equal widths ensures at most one same-width envelope is selected — any two same-width envelopes will have the taller one replacing the shorter in tails.
Interview Questions
Q: Why is the O(n log n) approach faster, and what guarantees tails stays sorted?
tails stays sorted because we only ever replace or append. Replacing: binary search finds the leftmost position where tails[pos] >= num; we replace tails[pos] with num (a smaller value). Since tails[pos-1] < num (by binary search property), tails stays sorted. Appending: num > tails[last], so appending preserves sorted order. Binary search on a sorted tails array is O(log n), and we process n elements: total O(n log n).
Q: How does the Russian Doll problem reduce to 1D LIS?
Sort envelopes by width ascending so wider envelopes come later. For equal widths, sort by height descending — this prevents picking multiple same-width envelopes (since LIS on descending heights can't pick two from the same group). Now run LIS on heights: an increasing height subsequence in this sorted order corresponds to envelopes that can be nested (each wider AND taller). The maximum such subsequence is the maximum number of nestable envelopes.
Q: For Number of LIS, what are the two update cases and what do they mean?
At position i, examining all j < i where nums[j] < nums[i]: Case 1: dp[j]+1 > dp[i] — found a longer LIS ending at i. Update dp[i] = dp[j]+1 and RESET cnt[i] = cnt[j]. All previous shorter subsequences are irrelevant; only the cnt[j] ways to reach length dp[j] and extend to i matter. Case 2: dp[j]+1 == dp[i] — another way to achieve the same LIS length ending at i. Add cnt[j] to cnt[i] — each of the cnt[j] subsequences ending at j can be extended by nums[i], giving cnt[j] more LIS of the same length ending at i.
Summary
LIS finds the longest subsequence where elements are strictly increasing.
Two approaches:
| O(n²) DP | O(n log n) patience | |
|---|---|---|
| State | dp[i] = LIS ending at i | tails[k] = min tail of IS of length k+1 |
| Answer | max(dp[i]) | len(tails) |
| Print? | Yes — parent[] array | Not directly (tails ≠ actual LIS) |
| When to use | Simpler; print needed | Length only; large n |
Key insight for O(n²): dp[i] = "LIS ending at i" — not "LIS in first i elements." The answer is max(dp), not dp[n-1].
Key insight for O(n log n): tails[k] stores the smallest possible ending element of any increasing subsequence of length k+1. Binary search finds where to place each element. Replacing gives smaller tails (more future flexibility); appending extends the LIS.
Five LIS-family problems:
| Problem | Insight | Key change |
|---|---|---|
| Number of LIS | cnt[i] tracks count; reset vs add | dp[j]+1>dp[i] → reset; ==dp[i] → add |
| Longest Bitonic | Peak divides increasing/decreasing | lis[i]+lds[i]-1; max over all peaks |
| Russian Doll | 2D LIS | Sort (w↑, h↓ on ties); LIS on heights |
| Non-decreasing | Allow equal | Change < to <= in comparison |
| Print LIS | parent[] backtracking | Record j that maximised dp[i]; backtrack |
In the next topic you will explore DP Time and Space Complexity — how to systematically derive complexity for any DP problem and apply space optimisations
LIS DP: dp[i] = length of LIS ENDING at index i. For nums=[3,1,8,2,5], what is dp[4] (ending at nums[4]=5)?