Algorithm of the day -

The Longest Increasing Subsequence (LIS) with Dynamic Programming

Summary

The Longest Increasing Subsequence algorithm is used to find the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Use Case

For example, given the sequence [10, 22, 9, 33, 21, 50, 41, 60, 80], the longest increasing subsequence is [10, 22, 33, 50, 60, 80].

Steps

  1. Define the problem and identify the input sequence.
  2. Initialize a dynamic programming table to store the lengths of the longest increasing subsequences ending at each position.
  3. Fill the dynamic programming table by comparing each element with all previous elements and update the table accordingly.
  4. Find the maximum length in the dynamic programming table, which represents the length of the longest increasing subsequence.
  5. Reconstruct the longest increasing subsequence by tracing back the dynamic programming table.

Complexity

The time complexity of the Longest Increasing Subsequence algorithm is O(n^2) and the space complexity is O(n), where n is the length of the input sequence.

Code Example

def longest_increasing_subsequence(sequence):
    n = len(sequence)
    dp = [1] * n
    prev = [-1] * n
    max_length = 1
    max_index = 0
    for i in range(1, n):
        for j in range(i):
            if sequence[i] > sequence[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j
        if dp[i] > max_length:
            max_length = dp[i]
            max_index = i
    subsequence = []
    while max_index != -1:
        subsequence.append(sequence[max_index])
        max_index = prev[max_index]
    return subsequence[::-1]
print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80]))