Longest Increasing Subsequence
Given an integer array, find the length of the longest strictly increasing subsequence.
DP Array (Length of LIS ending here)
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine you are jumping across stepping stones in a river, but you can only jump to a stone that is higher than the one you are currently on. You want to make the maximum number of jumps.
Concept
Dynamic Programming (O(N²)):
Let `dp[i]` be the length of the longest increasing subsequence ending at index `i`. To calculate `dp[i]`, we look at all previous indices `j < i`. If `nums[j] < nums[i]`, we can extend the subsequence ending at `j`. So, `dp[i] = max(dp[i], dp[j] + 1)`.
How it Works
Algorithm:
- Initialize `dp` array of size N with 1s.
- Iterate i from 1 to N-1.
- Inner loop j from 0 to i-1.
- If `nums[i] > nums[j]`, update `dp[i] = max(dp[i], dp[j] + 1)`.
- The answer is the maximum value in the entire `dp` array.
Step-by-Step Breakdown
Visualizing the 1D DP Array:
- Base State: Every element is an LIS of length 1 (itself).
- Extension: When we find a smaller previous element, we 'extend' its LIS.
- Result: The longest LIS isn't necessarily at the last index; it's the max of all `dp` values.
When to Use
Applications:
- Analyzing trends (stock market).
- Optimization problems where order matters.
- Layering or stacking problems (e.g., Russian Doll Envelopes).
When NOT to Use
- Contiguous Subarray: For contiguous subarrays, use Kadane's or Sliding Window.
- Arbitrary Order: If original order doesn't matter, just Sort and remove duplicates.
How to Identify
"Find longest sequence... strictly increasing... original order".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.