Longest Increasing Subsequence

See all coding puzzles and patterns here.

Leetcode 300
Difficulty: Medium
Patterns:
- Depth-First Search
- Dynamic Programming

Problem Definition

Given an array of numbers, find the longest strictly increasing subsequence in the array. The subsequence need not be contiguous.

Examples

Some test cases to verify our solution.

assert lis([1, 5, 2, 3, 4, 6]) == [1, 2, 3, 4, 6]
assert lis([1, 5, 6, 7, 2, 3, 8]) == [1, 5, 6, 7, 8]
assert lis([8, 7, 6]) == [8]
assert lis([]) == []
assert lis([5]) == [5]

Brute Force DFS Solution

For every element, either the element is in the longest subsequence or it's not. If it is, then the longest subsequence is that character plus the longest subsequence in the remainder of the array with that element as the floor. If it isn't, then the longest subsequence is just the longest subsequence in the remainder with the existing floor. We will do a depth-first search over the binary decision tree created by branching at each subsequent element.

def lis(arr):
    arr_len = len(arr)
    if arr_len < 2:
        return arr
    # processing queue
    # items of form (starting_index, value_floor, indexes_in_sequence)
    q = [(1, arr[0], (0,)), (2, arr[1], (1,))]
    max_so_far = (0,)
    while q:
         idx, floor, seq = q.pop()
         if len(seq) > len(max_so_far):
             max_so_far = seq
         if idx < arr_len:
             q.append((idx + 1, floor, seq))
             if arr[idx] > floor:
                 new_seq = seq + (idx,)
                 q.append(((idx + 1), arr[idx], new_seq))
    return [arr[idx] for idx in max_so_far]

DFS Solution Complexity

Let $n = $ len(arr).

Runtime complexity should be $\Theta(2^n)$ because we will look at every node in the binary decision tree.

Space complexity should be $\Theta(n)$ since this is a depth-first search, meaning we construct at most 2n nodes for processing at any time.

Dynamic Programming Solution

We can construct the solutions backwards, since $\forall j > i$, lis[i] = max_len(1, (arr[i],) + lis[j]) if arr[i] < lis[j].

def lis(arr):
    arr_len = len(arr)
    if arr_len < 2:
        return arr
    dp = [(x,) for x in arr]
    for idx in range(arr_len - 1, -1, -1):
        for jdx in range(idx + 1, arr_len):
            if arr[idx] < arr[jdx]:
                candidate = (arr[idx],) + dp[jdx]
                if len(candidate) > len(arr[idx]):
                    arr[idx] = candidate
    return max(dp)

Dynamic Programming Solution Complexity