Longest Increasing Subsequence
The Longest Increasing Subsequence (LIS) problem finds the length of the longest subsequence where elements are in strictly increasing order. It can be solved in O(n²) using DP or O(n log n) using patience sorting.
DP approach: dp[i] = max length ending at i = 1 + max(dp[j]) for all j < i with arr[j] < arr[i].
Java implementation (O(n²)):
public static int lis(int[] arr) {
int n = arr.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
The O(n log n) approach uses binary search on the tails array.
Two Minute Drill
- LIS finds longest strictly increasing subsequence.
- O(n²) DP: dp[i] = length ending at i.
- O(n log n) uses patience sorting and binary search.
- Used in many problems like building bridges, longest chain, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com