intermediate8 min read·Updated October 5, 2026

Longest Increasing Subsequence Explained: Tracing [10, 9, 2, 5, 3, 7, 101, 18]

Master the Longest Increasing Subsequence algorithm. Walk through the DP state and binary search approach on [10, 9, 2, 5, 3, 7, 101, 18] step by step.

By Learnisim AI·Published October 5, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • basic arrays
  • introductory dynamic programming
Longest Increasing Subsequence (LIS): nums = [10, 9, 2, 5, 3, 7, 101, 18] Phase 1: Raw Stream & Constraints (Original Relative Order Preserved) 10 9 2 5 3 7 101 18 Phase 2: DP Table State (dp[i] = max length ending at index i) Transition rule: dp[i] = 1 + max([dp[j] for j < i if nums[j] < nums[i]] + [0]) nums: dp: 10 1 9 1 2 1 5 2 3 2 7 3 101 4 18 4 Phase 3: Optimal Subsequence Extraction & Final Result Winning Increasing Chain (Length = 4): 2 3 7 18 (or ... 7 → 101) Maximum LIS Length = 4
LIS of [10, 9, 2, 5, 3, 7, 101, 18] overview diagram
Why

Why Order Matters: The Hidden Subsequence Problem

Phase 1: The Disordered Stream

Imagine you are handed a raw stream of inventory counts, sensor readings, or stock prices: nums = [10, 9, 2, 5, 3, 7, 101, 18]. You need to find the longest chain of values where each entry is strictly greater than the one before it. But there is a catch: you cannot rearrange the elements. You can only pick numbers out from left to right while preserving their original relative order.
At first glance, scanning left to right feels deceptive. We see 10, then 9 (which drops), then 2 (which drops further), before climbing up to 5, 3, 7, 101, and 18. If we just greedily grab the first numbers that look promising, or throw out everything that dips, we lose the larger picture. The sheer number of possible subsets— combinations—means a naive brute-force check will quickly choke as the array grows.
Without a structured way to remember what came before, we find ourselves constantly re-evaluating past decisions. We need a concept that lets us track valid increasing paths efficiently without inspecting every exponential combination by hand. That concept is the Longest Increasing Subsequence, and mastering it changes how we handle ordering constraints across computer science.
python
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# Try to manually trace one valid increasing subsequence
# e.g., [2, 3, 7, 18] has length 4. Can you find another?
Why Order Matters: The Longest Increasing Subsequence (LIS) Stream: nums = [10, 9, 2, 5, 3, 7, 101, 18] — pick strictly increasing elements preserving original relative order Raw Input Stream (No Rearranging) 10 idx 0 9 idx 1 2 idx 2 (Start) 5 idx 3 3 idx 4 7 idx 5 101 idx 6 18 idx 7 (Span) DP State: Max LIS ending at each index (dp[i]) 1 10 1 9 1 2 2 5 2 3 3 7 4 101 4 18 Recurrence: dp[i] = max(1 + max(dp[j])) for all j < i where nums[j] < nums[i] Optimal Solutions (Length = 4) [2, 3, 7, 18] Valid Chain A [2, 5, 7, 101] Max Element 101 ✕ Greedy & Brute-Force Trap Naive checks require exploring 2ⁿ combinations; greedy discards '2' on seeing drops like '10 → 9'. ✓ Preserving Relative Order Elements can be skipped, but never reordered. Each step builds on previously solved subproblems. ⚡ Efficient Solutions DP takes O(n²) time; Binary Search patience sorting drops complexity to O(n log n).
Why Order Matters: The Hidden Subsequence Problem diagram
Model

Building the Dynamic Programming Mental Model for LIS

Phase 2: The DP Table Model

When looking at our working sequence nums = [10, 9, 2, 5, 3, 7, 101, 18], a brute-force check of every combination fails because there are possible subsequences. Instead, we can model this as a cumulative building process using an array dp, where dp[i] represents the length of the longest increasing subsequence that ends specifically at index .
To compute dp[i], we look backward at all previous indices . If our current number nums[i] is strictly greater than a past number nums[j], it means we can legally append nums[i] to the end of the increasing subsequence that ended at . Thus, the transition rule becomes:
Every position starts with a baseline length of 1 (representing the element itself as a subsequence of length one). As we move through the array from left to right, each entry in dp crystallizes the best historical choice available from its left-hand neighbors.
Longest Increasing Subsequence (LIS) — DP Mental Model Working Sequence: nums = [10, 9, 2, 5, 3, 7, 101, 18] • Transition: dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i] nums: 10 i=0 9 i=1 2 i=2 5 i=3 3 i=4 7 i=5 (Active) 101 i=6 18 i=7 dp table: 1 1 1 2 2 3 4 4 1. The Backward Transition Logic • Base case: Every element is initially LIS = 1. • Inspect all past indices j < i (e.g., examining nums[5] = 7): - nums[3]=5 < 7 ⇒ dp[3] + 1 = 2 + 1 = 3 - nums[2]=2 < 7 ⇒ dp[2] + 1 = 1 + 1 = 2 - nums[4]=3 < 7 ⇒ dp[4] + 1 = 2 + 1 = 3 • Result: dp[5] = max(..., 3) = 3 (subsequence [2, 5, 7]) Avoids 2^n brute-force search by memoizing optimal subproblems. 2. Why DP Table Model Works • Cumulative Crystallization: Each dp[i] locks in the optimal historical choice from left-hand neighbors before moving forward. • Final Answer Extraction: max(dp) across the entire table gives the global LIS Max LIS length = 4 (e.g., [2, 3, 7, 18] or [2, 5, 7, 18]) Time Complexity: O(n²) standard DP • O(n log n) with binary search
Building the Dynamic Programming Mental Model for LIS diagram
Worked example

Tracing the DP Table and Binary Search for [10, 9, 2, 5, 3, 7, 101, 18]

Phase 3: Walking Through the Lock Sequence

Let us now apply our dynamic programming recurrence and the optimized tails approach to our locked array: nums = [10, 9, 2, 5, 3, 7, 101, 18]. Our goal is to find the length of the longest strictly increasing subsequence.
Given:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Steps (Classic DP Table Trace):
1. Initialize a dp array of the same length, where every entry is 1 because any single element is an increasing subsequence of length 1.
2. For each element at index i, check all previous elements j (where j < i). If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).
Here is how the dp array evolves step by step across each element:
Initial: nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp = [ 1, 1, 1, 1, 1, 1, 1, 1]
i = 0 (10): dp[0] = 1
i = 1 (9): 9 not > 10. dp[1] = 1
i = 2 (2): 2 not > 10, 9. dp[2] = 1
i = 3 (5): 5 > 2 (dp[2]=1). dp[3] = max(1, 1+1) = 2. dp = [1, 1, 1, 2, 1, 1, 1, 1]
i = 4 (3): 3 > 2 (dp[2]=1). dp[4] = max(1, 1+1) = 2. dp = [1, 1, 1, 2, 2, 1, 1, 1]
i = 5 (7): 7 > 2, 5, 3. Max from dp[3] or dp[4] is 2. dp[5] = 2 + 1 = 3.
i = 6(101): 101 > all previous. Max dp is dp[5]=3. dp[6] = 3 + 1 = 4.
i = 7 (18): 18 > 10,9,2,5,3,7. Max dp is dp[5]=3 (from 7). dp[7] = 3 + 1 = 4.
Result:
The maximum value in our final dp table is 4 (found at indices 6 and 7). Thus, the length of the longest increasing subsequence for this sequence is 4.
python
def lis_length(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
Phase 3: Walking Through the O(n²) DP Table Trace nums = [10, 9, 2, 5, 3, 7, 101, 18] — dp[i] = max(dp[i], dp[j] + 1) when nums[j] < nums[i] Index i i=0 i=1 i=2 i=3 i=4 i=5 i=6 i=7 nums[i] 10 9 2 5 3 7 101 18 dp[i] 1 1 1 2 2 3 4 4 Inner Loop Transition Rule: For each element i, we check all previous elements j (j < i). If nums[j] < nums[i], we take max(dp[i], dp[j] + 1). Example: i=5 (val 7) looks back at nums[2]=2, [3]=5, [4]=3. Final Result Extraction: The maximum value in our completed dp table is 4. Found at indices 6 (val 101) and 7 (val 18). Therefore, the length of the longest increasing subsequence is 4. Phase 3 Implementation (O(n²) DP Loop): dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # Output: 4
Tracing the DP Table and Binary Search for [10, 9, 2, 5, 3, 7, 101, 18] diagram
Practice

Predicting the LIS Table State and Output on a Modified Input

Phase 4: Practice Your LIS Tracing Skills

Now it is time to test your mental model against a slight mutation of our working example. Recall our original sequence nums = [10, 9, 2, 5, 3, 7, 101, 18] which resulted in an LIS length of 4. Let us replace the middle elements to see how the recurrence reacts.
Consider the new sequence nums = [2, 15, 3, 7, 8, 6, 18]. Walk through the dynamic programming table or the tails array approach step by step. For each incoming number, determine whether it extends an existing subsequence or overwrites a tail value.
Keep track of the intermediate tails array state as you process each number from left to right. This hands-on trace bridges the gap between passive reading and active algorithmic mastery.
python
def solve_lis_practice(nums):
    # Trace your tails array or dp table here for nums = [2, 15, 3, 7, 8, 6, 18]
    pass
Apply

Transferring the LIS Approach to Non-Array Domains

Phase 5: Applying LIS Beyond Simple Arrays

Now that we have traced our working example [10, 9, 2, 5, 3, 7, 101, 18] and verified our understanding on edge variations, we can recognize that the core pattern—maintaining smallest possible tails for each subsequence length via binary search—is not restricted to raw numeric arrays. Consider a logistics problem where you receive a stream of rectangular crates, each defined by a width and a height. You want to find the longest sequence of crates that can be nested inside one another, where crate A fits inside crate B strictly if both its width and height are smaller.
By sorting the crates primarily by width in ascending order (and handling width ties by sorting heights in descending order), the two-dimensional nesting problem reduces directly to finding the Longest Increasing Subsequence of their heights! The recurrence relation we built for nums seamlessly translates to this new domain because the sorting eliminates one dimension of uncertainty. Whenever you see a problem asking for a maximal chain of compatible elements where transitivity holds, you are looking at an LIS variant.
python
def max_nested_crates(crates):
    # crates is a list of [width, height]
    crates.sort(key=lambda x: (x[0], -x[1]))
    heights = [c[1] for c in crates]
    # Apply our LIS tails binary search on heights
    import bisect
    tails = []
    for h in heights:
        idx = bisect.bisect_left(tails, h)
        if idx == len(tails):
            tails.append(h)
        else:
            tails[idx] = h
    return len(tails)
Whenever structural constraints force data into a partial order, mapping those constraints into an indexable sequence unlocks the exact same efficiency we discovered in our original working example.
python
def solve_transfer_challenge():
    # Given a list of envelopes [width, height]:
    # [[5, 4], [6, 4], [6, 7], [2, 3]]
    # Explain how sorting and applying the LIS tails strategy finds the max nesting count.
    pass

FAQ

What is the Longest Increasing Subsequence for [10, 9, 2, 5, 3, 7, 101, 18]?
The length of the LIS is 4. Valid subsequences of length 4 include [2, 3, 7, 101] and [2, 5, 7, 18].
Why can't we just sort the array to find the LIS?
Sorting alters the original relative order of elements. A subsequence must maintain the original left-to-right sequence of elements from the array, just without necessarily being contiguous.
What is the time complexity of the optimized LIS algorithm?
Using dynamic programming with binary search (Patience Sorting approach), the time complexity is O(N log N), compared to the O(N^2) naive DP approach.
What is the difference between a subarray, substring, and subsequence?
A subarray or substring consists of contiguous elements. A subsequence can skip elements, but must maintain their relative order.

Keep learning