Longest Increasing Subsequence (LIS) - Algorithm Tutorial | Repovive

Longest Increasing Subsequence (LIS) Algorithm Tutorial

mediumdpdata structures2 min read

Introduction

The Longest Increasing Subsequence (LIS) problem asks for the length of the longest subsequence where each element is strictly greater than the previous one.

Example: For array $[10, 9, 2, 5, 3, 7, 101, 18]$ :

$[2, 5, 7, 101]$ is an increasing subsequence of length 4
$[10, 101]$ is an increasing subsequence of length 2
The LIS has length 4

Applications:

Patience sorting algorithm
Box stacking problems
Longest chain problems in DAGs
Version control (finding longest common history)

DP Approach (O(n²))

Define $dp[i]$ as the length of the LIS ending at index $i$ .

Recurrence: $dp[i] = 1 + \max_{j < i, a_j < a_i} dp[j]$

If no valid $j$ exists, $dp[i] = 1$ (the element itself forms an LIS of length 1).

Algorithm:

text

function lis_dp(a):
    n = length(a)
    dp = array of size n, all initialized to 1

    for i from 1 to n-1:
        for j from 0 to i-1:
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Time: $O(n^2)$ , Space: $O(n)$

Binary Search Approach (O(n log n))

Maintain an array $tails$ where $tails[i]$ stores the smallest tail element for all increasing subsequences of length $i+1$ .

Key insight: $tails$ is always sorted, so we can use binary search.

Algorithm:

text

function lis_binary(a):
    tails = empty array

    for each num in a:
        pos = binary_search(tails, num)  // find first >= num
        if pos == length(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return length(tails)

Why it works: By keeping the smallest possible tail for each length, we maximize the chance of extending the subsequence.

Time: $O(n \log n)$ , Space: $O(n)$

Trace Through Example

Array: $[10, 9, 2, 5, 3, 7, 101, 18]$

Using the binary search approach:

Step	num	tails (before)	Action	tails (after)
1	10	[]	append	[10]
2	9	[10]	replace at 0	[9]
3	2	[9]	replace at 0	[2]
4	5	[2]	append	[2, 5]
5	3	[2, 5]	replace at 1	[2, 3]
6	7	[2, 3]	append	[2, 3, 7]
7	101	[2, 3, 7]	append	[2, 3, 7, 101]
8	18	[2, 3, 7, 101]	replace at 3	[2, 3, 7, 18]

Final length: 4

Note: $tails$ is NOT the actual LIS. It just tracks the optimal tails.

Reconstructing the LIS

Implement this Algorithm

Go to Problem

Related Algorithms

2D Difference Painting

To find the actual LIS (not just its length), track the predecessor of each element.

text

function lis_with_reconstruction(a):
    n = length(a)
    dp = array of size n, all 1
    parent = array of size n, all -1

    for i from 1 to n-1:
        for j from 0 to i-1:
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j

    // Find ending position of LIS
    end_pos = index of max(dp)

    // Backtrack to build LIS
    lis = []
    pos = end_pos
    while pos != -1:
        lis.prepend(a[pos])
        pos = parent[pos]

    return lis

For the $O(n \log n)$ approach, reconstruction requires storing indices alongside values in $tails$ .