LIS
← Back to Classic Problems (DP)
Longest Increasing Subsequence: find the longest subsequence of a sequence in which elements are in strictly increasing order. Can be solved in O(n^2) with DP or O(n log n) with patience sorting / binary search. Applications in scheduling and sequence analysis.