Dynamic Programming - Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence (LIS) problem is a classic algorithmic challenge in the field of Computer Science and Dynamic Programming. The goal is to find the longest subsequence of a given sequence of numbers where the elements are in strictly increasing order.

Problem Statement

Given a sequence of numbers, find the length of the longest increasing subsequence.

For example, given the sequence [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101], and its length is 4.

Solution Approach

The LIS problem can be solved using various methods, including:

Recursive Approach: This approach has exponential time complexity and is not practical for large sequences.
Dynamic Programming with Binary Search: This approach has O(n log n) time complexity and is more efficient for larger sequences.
Dynamic Programming with Two Arrays: This approach also has O(n log n) time complexity and uses two arrays to track the subsequences.

Below is an example of the Dynamic Programming with Binary Search approach to solve the LIS problem:

def longest_increasing_subsequence(sequence):
    subseq = [sequence[0]]
    for i in range(1, len(sequence)):
        if sequence[i] > subseq[-1]:
            subseq.append(sequence[i])
        else:
            # Binary search to find the smallest element in subseq which is greater than or equal to sequence[i]
            left, right = 0, len(subseq) - 1
            while left < right:
                mid = (left + right) // 2
                if subseq[mid] < sequence[i]:
                    left = mid + 1
                else:
                    right = mid
            subseq[right] = sequence[i]
    return len(subseq)

# Example usage
sequence = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(sequence))

For more detailed explanations and examples, you can visit the Dynamic Programming page.