Definition
- LIS (Longest Increasing Subsequence) – the longest subsequence of elements in strictly increasing order, not necessarily contiguous.
- Tabulation – fill an array where len[i] = length of LIS ending exactly at index i.
- Recurrence – for each i, scan all j < i where nums[j] < nums[i]; set len[i] = max(len[j] + 1).
- Predecessor – prev[i] records which j gave the best len[i], enabling reconstruction by walking backward.
- Complexity – O(n^2) time, O(n) space for the len and prev arrays.
The National Bank of India wants the longest run of strictly rising monthly balances in a customer's history, and needs to cite exactly which months formed that run for a credit report.
Understanding the Concepts
What is the Longest Increasing Subsequence?
The LIS of a sequence is the longest subsequence where each element is strictly greater than the previous. Elements need not be contiguous. For example, in [3, 4, 1, 5], the LIS is [3, 4, 5] with length 3.
At the National Bank of India, a credit analyst reviews Rajesh's monthly balances and needs the longest streak of strictly increasing months to demonstrate consistent growth.
package com.bank.credit;
import java.util.*;
public class LISDemo {
public static void main(String[] args) {
int[] balances = {10000, 15000, 8000, 20000, 25000, 12000, 30000};
System.out.println("LIS length: " + lisLength(balances));
System.out.println("LIS months: " + lisReconstruct(balances));
}
// implementation below
}
How does the quadratic tabulation work?
Create a length array where every entry starts at 1 (a single element is an LIS of length 1). For each index i, scan all earlier indices j. If nums[j] < nums[i] and len[j] + 1 > len[i], update len[i] and record j as the predecessor.
package com.bank.credit;
public class LISTabulation {
static int lisLength(int[] nums) {
int n = nums.length;
int[] len = new int[n];
Arrays.fill(len, 1);
int best = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
}
}
best = Math.max(best, len[i]);
}
return best;
}
public static void main(String[] args) {
int[] nums = {3, 4, 1, 5};
System.out.println("LIS length: " + lisLength(nums));
}
}
LIS length: 3
How do you reconstruct the actual subsequence?
Maintain a predecessor array prev[] initialized to -1. During the fill, when len[i] is updated from j, set prev[i] = j. After the fill, find the index with the best length. Walk backward from that index following prev[] links, collecting values, then reverse them.
package com.bank.credit;
import java.util.*;
public class LISReconstruct {
static List<Integer> lisReconstruct(int[] nums) {
int n = nums.length;
int[] len = new int[n];
int[] prev = new int[n];
Arrays.fill(len, 1);
Arrays.fill(prev, -1);
int bestLen = 1, bestIdx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
prev[i] = j;
}
}
if (len[i] > bestLen) {
bestLen = len[i];
bestIdx = i;
}
}
// Walk backward to reconstruct
List<Integer> lis = new ArrayList<>();
int idx = bestIdx;
while (idx != -1) {
lis.add(nums[idx]);
idx = prev[idx];
}
Collections.reverse(lis);
return lis;
}
public static void main(String[] args) {
int[] balances = {10000, 15000, 8000, 20000, 25000, 12000, 30000};
List<Integer> lis = lisReconstruct(balances);
System.out.println("LIS: " + lis);
System.out.println("Length: " + lis.size());
}
}
LIS: [10000, 15000, 20000, 25000, 30000]
Length: 5
How does the fill work step by step?
For balances [3, 4, 1, 5]: - i=0: len[0]=1 (base case) - i=1: j=0: nums[0]=3 < 4, len[0]+1=2 > 1 -> len[1]=2, prev[1]=0 - i=2: j=0: nums[0]=3 > 1, skip. j=1: nums[1]=4 > 1, skip. len[2]=1 - i=3: j=0: 3 < 5, len[0]+1=2. j=1: 4 < 5, len[1]+1=3 > 2 -> len[3]=3, prev[3]=1. j=2: 1 < 5, len[2]+1=2 < 3, skip.
package com.bank.credit;
import java.util.Arrays;
public class LISStepByStep {
public static void main(String[] args) {
int[] nums = {3, 4, 1, 5};
int n = nums.length;
int[] len = new int[n];
int[] prev = new int[n];
Arrays.fill(len, 1);
Arrays.fill(prev, -1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
prev[i] = j;
}
}
System.out.println("i=" + i + " len=" + Arrays.toString(len)
+ " prev=" + Arrays.toString(prev));
}
}
}
i=1 len=[1, 2, 1, 1] prev=[-1, 0, -1, -1]
i=2 len=[1, 2, 1, 1] prev=[-1, 0, -1, -1]
i=3 len=[1, 2, 1, 3] prev=[-1, 0, -1, 1]
How does this compare to the O(n log n) patience method?
The patience method uses binary search to maintain a tails array, achieving O(n log n) time. However, it only gives the LIS length directly. Reconstructing the actual subsequence requires extra bookkeeping. The quadratic method naturally supports reconstruction via the prev array.
| Method | Time | Space | Reconstruction |
|--------|------|-------|----------------|
| Quadratic tabulation | O(n^2) | O(n) | Natural via prev[] |
| Patience (binary search) | O(n log n) | O(n) | Extra bookkeeping needed |
// Patience method (length only, O(n log n)):
int[] tails = new int[n];
int size = 0;
for (int num : nums) {
int pos = Arrays.binarySearch(tails, 0, size, num);
if (pos < 0) pos = -(pos + 1);
tails[pos] = num;
if (pos == size) size++;
}
// size is the LIS length
What are the edge cases?
Edge cases include a single element (LIS = 1), a strictly increasing array (LIS = n), a strictly decreasing array (LIS = 1), and duplicate values (LIS is strictly increasing, so duplicates do not extend it).
package com.bank.credit;
public class LISEdgeCases {
public static void main(String[] args) {
System.out.println(lisLength(new int[]{5})); // 1
System.out.println(lisLength(new int[]{1, 2, 3, 4})); // 4
System.out.println(lisLength(new int[]{4, 3, 2, 1})); // 1
System.out.println(lisLength(new int[]{3, 3, 3})); // 1 (strictly increasing)
}
static int lisLength(int[] nums) {
int n = nums.length;
int[] len = new int[n];
java.util.Arrays.fill(len, 1);
int best = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && len[j] + 1 > len[i]) len[i] = len[j] + 1;
}
best = Math.max(best, len[i]);
}
return best;
}
}
1
4
1
1
What are common mistakes?
The most common mistake is forgetting to initialize every len[] entry to 1. Without this, the base case (single element = LIS of 1) is missing and all lengths would be 0.
// WRONG: len[] defaults to 0
int[] len = new int[n]; // all zeros
// len[i] never starts at 1, so LIS of a single element would be 0
// CORRECT: initialize to 1
int[] len = new int[n];
Arrays.fill(len, 1);
What should a senior engineer know?
- When to use quadratic vs patience. Use the quadratic method when you need the actual subsequence or when n is small (under ~10,000). Use patience for large n when only the length is needed.
- Non-strictly increasing. For non-decreasing (allow equal), change the condition from
<to<=. This matters for problems like Russian Doll Envelopes. - 2D LIS. The Longest Increasing Subsequence in 2D (e.g., sorting by one dimension and finding LIS in the other) is a common follow-up.
- Real credit analysis. In banking, the actual months matter more than the count, because the credit report must cite specific improving periods.
Visual Overview
Input: [10000, 15000, 8000, 20000, 25000, 12000, 30000]
Index: 0 1 2 3 4 5 6
len[]: [ 1, 2, 1, 3, 4, 2, 5 ]
prev[]: [-1, 0, -1, 1, 3, 2, 4 ]
Best length: 5 at index 6
Reconstruction (walk prev[] backward):
idx=6: 30000, prev=4
idx=4: 25000, prev=3
idx=3: 20000, prev=1
idx=1: 15000, prev=0
idx=0: 10000, prev=-1 (stop)
Reverse: [10000, 15000, 20000, 25000, 30000]
Key Takeaway
The quadratic tabulation for the Longest Increasing Subsequence is the version I reach for when I need the actual elements, not merely the length. I keep a length array where each entry holds the LIS length ending exactly at that index, starting every entry at 1. For each index, I scan all earlier indices, and whenever an earlier value is smaller and extending its run beats my current best, I update my length and record that earlier index as my predecessor.
The predecessor array makes reconstruction clean. After the fill, I know the best overall length and the ending index. I follow predecessor links backward, collecting each value, then reverse the list. The whole process is O(n^2) time and O(n) space.
The patience-sorting method gives O(n log n) time, which is faster for large inputs, but it only yields the length without extra bookkeeping. When the actual subsequence matters, the quadratic approach is simpler and more natural.
At the National Bank of India, a credit report needed to cite the exact months where Rajesh's balance strictly rose. I ran the quadratic fill over monthly balances and followed the predecessor chain to produce the list of improving months.
Remember one sentence: len[i] = 1 + the best len[j] where nums[j] < nums[i] and j < i, and prev[i] = j lets you walk backward to reconstruct the actual increasing subsequence.
---