Python Program to Find the Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem asks: given an array of numbers, what's the length of the longest subsequence where every element is strictly greater than the one before it, keeping the original order but allowed to skip elements? For example, in [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 18] (or [2, 3, 7, 101]), with length 4. It's a classic dynamic programming problem that regularly shows up in technical interviews, and the same pattern applies to real problems like finding the longest streak of improving values in a time series.

Python Program to Find the Longest Increasing Subsequence

def longest_increasing_subsequence(nums):
    if not nums:
        return 0, []

    n = len(nums)
    # dp[i] = length of the longest increasing subsequence ENDING at index i
    dp = [1] * n
    # previous[i] = index before i in that subsequence, used to rebuild it
    previous = [-1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                previous[i] = j

    # Find where the longest subsequence ends
    max_length = max(dp)
    end_index = dp.index(max_length)

    # Walk backward through `previous` to rebuild the actual subsequence
    sequence = []
    while end_index != -1:
        sequence.append(nums[end_index])
        end_index = previous[end_index]
    sequence.reverse()

    return max_length, sequence


numbers = [10, 9, 2, 5, 3, 7, 101, 18]
length, sequence = longest_increasing_subsequence(numbers)
print(f"LIS length: {length}")
print(f"LIS: {sequence}")

Output:

LIS length: 4
LIS: [2, 3, 7, 18]

For every index i, dp[i] asks "what's the longest increasing subsequence that ends exactly here?" by checking every earlier index j — if nums[j] is smaller than nums[i], we could extend that subsequence by one. Because of the nested loop, this runs in O(n²) time and O(n) space. There's a faster O(n log n) approach using binary search over a list of "smallest tail values," but the O(n²) DP version above is the one most interviewers expect first, since it's easier to reason about and extend — for example to the related Longest Common Subsequence problem, which uses the same "table of subproblem answers" idea on two strings instead of one array.

---