Longest Increasing Subsequence (LIS) - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/lis

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/lis

Repovive

Longest Increasing Subsequence (LIS) - Algorithm Tutorial | Repovive | Repovive

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:

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:

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

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

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$ .

Longest Increasing Subsequence (LIS) Algorithm Tutorial

Introduction

Practice this Algorithm

Related Algorithms

DP Approach (O(n²))

Binary Search Approach (O(n log n))

Trace Through Example

Reconstructing the LIS