Longest Increasing Subsequence

DSA · Dynamic Programming

Theory

The longest increasing subsequence (LIS) is the longest sequence of elements taken from an array, in their original order but not necessarily adjacent, where each element is larger than the previous one. For [10, 9, 2, 5, 3, 7, 101, 18] one LIS is [2, 3, 7, 18], so the answer is 4. The DP solution sets dp[i] to the length of the longest increasing subsequence ending at index i and checks every earlier j with a smaller value: dp[i] = 1 + max(dp[j]). That takes O(n^2). A smarter O(n log n) method keeps an array tails where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1, and uses binary search to place each new number.

Why we use it

LIS is a classic interview problem that shows both a straightforward DP and an optimisation with binary search. It models problems like nesting boxes, scheduling and stacking.

When to use it

Use the O(n^2) DP for small inputs or when you need to reconstruct the subsequence easily; use the binary search version for large arrays.

How it works

  1. tails = []
  2. For each x
  3. i = position of x in tails (binary search)
  4. i == len(tails)? Yes: Append x. No: Replace tails[i] with x.
  5. Length = len(tails)

Syntax

DP:      dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i])   O(n^2)
Tails:   bisect_left(tails, x) per element                   O(n log n)

Example

from bisect import bisect_left

nums = [10, 9, 2, 5, 3, 7, 101, 18]

# O(n^2) DP with reconstruction
n = len(nums)
dp, prev = [1] * n, [-1] * n
for i in range(n):
    for j in range(i):
        if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
            dp[i], prev[i] = dp[j] + 1, j
end = max(range(n), key=lambda i: dp[i])
seq = []
while end != -1:
    seq.append(nums[end]); end = prev[end]
print("dp:", dp)
print("LIS:", seq[::-1], "length", len(seq))

# O(n log n) with binary search
tails = []
for x in nums:
    i = bisect_left(tails, x)
    if i == len(tails):
        tails.append(x)
    else:
        tails[i] = x
    print(f"after {x:>3}: tails = {tails}")
print("Length:", len(tails))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic