Program Explanation

The problem of finding the Longest Increasing Subsequence (LIS) in an array can be solved using dynamic programming. The idea is to use an array to store the length of the longest increasing subsequence ending at each index of the array.

Here’s a step-by-step explanation of the program:

1. Initialize an array: We use an array dp where dp[i] represents the length of the longest increasing subsequence ending at index i. Initialize each dp[i] to 1 because the minimum length of LIS ending at each index is 1 (the element itself).
2. Fill the dp array: Iterate through each pair of indices (i, j) where i > j. If arr[i] is greater than arr[j], update dp[i] as max(dp[i], dp[j] + 1). This means that if arr[i] can extend the subsequence ending at arr[j], then dp[i] should be the maximum length of LIS ending at i.
3. Find the maximum length: The length of the longest increasing subsequence in the entire array is the maximum value in the dp array.

Python Program

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

    Parameters:
    arr (list): The input array of integers.

    Returns:
    int: The length of the longest increasing subsequence.
    """
    n = len(arr)
    if n == 0:
        return 0

    # Initialize the dp array where dp[i] will hold the length of LIS ending at index i
    dp = [1] * n

    # Compute the LIS values in a bottom-up manner
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # The length of the longest increasing subsequence is the maximum value in dp array
    return max(dp)

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

Documentation

Function: longest_increasing_subsequence(arr)

• Parameters:
  • arr (list): The input list of integers.
• Returns:
  • int: The length of the longest increasing subsequence.

Example: Given the array [10, 22, 9, 33, 21, 50, 41, 60, 80], the function returns 6, which corresponds to the longest increasing subsequence [10, 22, 33, 50, 60, 80].