Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem involves finding the longest subsequence in a given sequence of numbers where each element is greater than the previous one. Here’s how you can solve it using Python:

Program Structure

The program uses dynamic programming to solve the LIS problem efficiently. It involves creating an array to store the length of the longest increasing subsequence ending at each position in the input array.

Python Code

def longest_increasing_subsequence(arr):
    """
    Function to find the longest increasing subsequence in an array.

    :param arr: List[int] - The input array
    :return: List[int] - The longest increasing subsequence
    """
    if not arr:
        return []

    n = len(arr)
    # Initialize the LIS array where lis[i] stores the length of the LIS ending at index i
    lis = [1] * n
    # Initialize the previous index array to reconstruct the LIS
    prev = [-1] * n

    # Fill the LIS array and prev array
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
                prev[i] = j

    # Find the maximum length and index
    max_len = max(lis)
    max_index = lis.index(max_len)

    # Reconstruct the longest increasing subsequence
    longest_subseq = []
    while max_index != -1:
        longest_subseq.append(arr[max_index])
        max_index = prev[max_index]
    
    # The subsequence is constructed in reverse order, so reverse it
    return longest_subseq[::-1]

# Example usage
if __name__ == "__main__":
    array = [10, 22, 9, 33, 21, 50, 41, 60, 80]
    result = longest_increasing_subsequence(array)
    print("Longest Increasing Subsequence:", result)
    

Explanation

• Initialization: We start by initializing two arrays: lis to keep track of the length of the longest increasing subsequence up to each index and prev to reconstruct the sequence.
• Dynamic Programming: For each element in the array, we check all previous elements to update the lis array and record the predecessor index in prev.
• Reconstruction: After computing the lengths, we find the index of the maximum length and use the prev array to reconstruct the LIS in reverse order.