Longest Common Subsequence (LCS)

# Implementing the Longest Common Subsequence (LCS) using Dynamic Programming

def find_lcs(seq1, seq2):

    n = len(seq1)

    m = len(seq2)

    

    # Initialize a DP table with zeros

    dp = [[0] * (m + 1) for _ in range(n + 1)]

    

    # DP step: fill in the table

    for i in range(1, n + 1):

        for j in range(1, m + 1):

            if seq1[i-1] == seq2[j-1]:

                dp[i][j] = dp[i-1][j-1] + 1

            else:

                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    

    # Reconstruct the LCS

    lcs = []

    i, j = n, m

    while i > 0 and j > 0:

        if seq1[i-1] == seq2[j-1]:

            lcs.append(seq1[i-1])

            i -= 1

            j -= 1

        elif dp[i-1][j] > dp[i][j-1]:

            i -= 1

        else:

            j -= 1

    

    return lcs[::-1]  # Reverse the LCS to get it in the correct order



# Test the function

seq1 = [1, 2, 3, 4, 5]

seq2 = [6, 7, 1, 2, 8]

print(find_lcs(seq1, seq2))  # Should return [1, 2]