LIS Sequence
AlgorithmsMediumFind the longest increasing subsequence in an array of numbers.
Alt+Shift+I
Configuration Panel
LIS DP Array Nodes (path highlights)
Time Complexity
O(N^2) / O(N log N) optimized
Space Complexity
O(N) tables storage size
Conceptual Overview
The Longest Increasing Subsequence (LIS) problem finds the length of the longest subsequence in a given sequence such that all elements of the subsequence are sorted in increasing order.
Recurrence Relation
dp[i] = 1 + max(dp[j]) for all j < i where arr[j] < arr[i]
State Transitions
Decides to extend an increasing path ending at j with element i if element i is larger than element j.
Source: CP-Algorithms dynamic programming reference