codaBack to Academy
dynamic programming
Longest Increasing Subsequence
The Longest Increasing Subsequence (LIS) problem finds the length of the longest subsequence in an array where elements are in strictly increasing order. A classic O(n²) DP approach builds a table where dp[i] is the LIS length ending at index i. An optimized O(n log n) approach uses a patience sorting technique with binary search to maintain the smallest possible tail elements. This is a fundamental problem in combinatorics and sequence analysis.
Use Cases
- •Stock market analysis for identifying longest upward trends
- •Version control for finding longest chain of compatible updates
- •Bioinformatics for gene sequence alignment and analysis
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n log n) | O(n log n) | O(n log n) |
| Space | O(n) | ||
Visualization
| F(0) | F(1) | F(2) | F(3) | F(4) | F(5) | F(6) | F(7) | F(8) | F(9) | F(10) | |
|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Implementation
Output
Click "Run Code" to see output...