AI engineering glossary · Data structures algorithms
What is LIS (longest increasing subsequence)?
Longest increasing subsequence (also called LIS): The longest subsequence of a sequence whose values strictly increase from left to right, with items possibly not adjacent. It is solved in O(n^2) by dynamic programming or O(n log n) with binary search.
Longest increasing subsequence: an example
In [10, 9, 2, 5, 3, 7, 101, 18] one longest increasing subsequence is 2, 3, 7, 18 with length 4.
Related terms
More Data structures algorithms terms
- LRU cache
- Master theorem
- Memoization
- Merge sort
- Minimum spanning tree
- Monotonic stack
- NP-complete
- Open addressing
Where you learn it
Longest increasing subsequence is part of the AI Engineering Program, which teaches it with notes, a hands-on lab and an exam. The first lesson is free.