Longest Increasing Subsequence (LIS) Explained
Learn the LIS algorithm with dynamic programming. Compare O(n²) and O(n log n) solutions using patience sorting.
Visualize LIS dynamic programming solution step by step.
Home → CS Student Hub → Longest Increasing Subsequence
The longest increasing subsequence (LIS) problem asks: given a sequence of numbers, find the length of the longest subsequence where elements are in strictly increasing order. This is a classic LIS dynamic programming problem with both O(n²) and O(n log n) solutions.
📌 Example: [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 101] → Length = 4
Patience sorting LIS achieves O(n log n) time complexity.
From Student to Founder
Pass your exams now. When you're ready to start your own IT business, we provide the infrastructure — no loans, no debt, no equity loss.
Learn How We Help Founders →LIS Dynamic Programming Visualizer
Enter a sequence to find the longest increasing subsequence and visualize the DP solution.
LIS Example: [10, 9, 2, 5, 3, 7, 101, 18]
Walk through a complete LIS example step by step.
Step 1 (O(n²) DP): dp[i] = length of LIS ending at position i
Step 2 (Recurrence): dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i] Step 3: After computing all dp[i], take the maximum value Step 4 (Patience Sorting): Place each number on the leftmost pile where top card ≥ current numberAnswer: LIS length = 4 (subsequence: [2, 3, 7, 101] or [2, 5, 7, 101] or [2, 3, 7, 18])
LIS Algorithm Explained
Understanding the longest increasing subsequence algorithm and both solution approaches.
O(n²) Dynamic Programming
Create a dp array where dp[i] = length of LIS ending at index i. For each i, check all previous j where nums[j] < nums[i] and take the maximum dp[j] + 1. Time complexity O(n²).
O(n log n) Patience Sorting
Maintain piles where each new number is placed on the leftmost pile with top card ≥ current number. The number of piles equals the LIS length. Use binary search for O(n log n) complexity.
Backtrack to Find LIS
After computing dp values, trace backwards to reconstruct the actual longest increasing subsequence, not just its length.
Free LIS Cheat Sheet
Printable PDF with recurrence relation, O(n²) DP algorithm, O(n log n) patience sorting, complexity comparison, and practice problems.
📥 Download LIS Cheat Sheet (PDF)No email required. Instant download.
Frequently Asked Questions
Common questions about the longest increasing subsequence and LIS algorithm.
What is the longest increasing subsequence (LIS) problem?
The longest increasing subsequence problem asks: given a sequence of numbers, find the length of the longest subsequence where elements are in strictly increasing order. The subsequence doesn't need to be contiguous.
What is the time complexity of LIS?
There are two common solutions: O(n²) using dynamic programming, and O(n log n) using patience sorting with binary search.
How does patience sorting work for LIS?
Patience sorting LIS maintains piles where each new number is placed on the leftmost pile with top card ≥ current number. The number of piles at the end equals the LIS length. This method runs in O(n log n).
What's the recurrence relation for LIS DP?
The LIS dynamic programming recurrence is: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i], with dp[i] initialized to 1.
Is this LIS visualizer free?
Yes! This LIS algorithm visualizer is completely free. No signup, no ads. Just open the tool and start learning.
Additional Resources
Explore more algorithm visualizers and study guides.
Still Stuck on LIS?
Whether it’s the LIS algorithm, DP recurrence, or patience sorting — submit your question and we’ll send you a step-by-step solution.
Submit Your Question — Get a Step-by-Step Solution
One of our CS experts will review your problem and send you a detailed, step-by-step explanation within 24-48 hours. Free. No strings attached.
📋 Before you submit:
- Be specific about the sequence you’re trying to solve
- Share where exactly you’re getting stuck (DP table? recurrence?)
- Include any steps you’ve already completed
Fill out the form below
🔒 Your email is safe with us. We’ll never share your information. Questions may be anonymized and added to our FAQ to help other students.
⚠️ Important Disclaimer
This form is for educational assistance only. We aim to respond within 24-48 hours, but response times may vary based on volume.
While we strive to provide accurate, step-by-step explanations, we cannot guarantee the correctness of every solution. Our guidance is meant to help you learn — not to replace your own work or your professor’s instruction.
For urgent exam questions, please consult your professor or teaching assistant. We do not provide last-minute solutions.
Get More DP Resources First
Be the first to know when new visualizers, guides, and calculators are released. No spam, just helpful content.
We respect your privacy. Unsubscribe anytime.
© 2025 MarxisSolution | The Framework | The Solution | Contact
Pass your exams now. Launch your IT business later with infrastructure, not loans.