Python - Longest Increasing Subsequence

Python – Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is a classic dynamic programming challenge. The goal is to find the length of the longest subsequence of a given array such that all elements of the subsequence are sorted in increasing order. This tutorial will walk you through the problem statement, sample inputs/outputs, solution steps, and a Python program using dynamic programming.

Problem Statement

Given an array of integers, find the length of the longest increasing subsequence (LIS). A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

For example, if the input array is [10, 9, 2, 5, 3, 7, 101, 18], one of the longest increasing subsequences is [2, 3, 7, 101] with a length of 4.

Sample Input and Output

Example 1:

</>

Copy

# Input:
arr = [10, 9, 2, 5, 3, 7, 101, 18]

# Output:
4

# Explanation:
# The longest increasing subsequence is [2, 3, 7, 101], which has length 4.

Example 2:

</>

Copy

# Input:
arr = [0, 1, 0, 3, 2, 3]

# Output:
4

# Explanation:
# One of the longest increasing subsequences is [0, 1, 2, 3], which has length 4.

Solution Approach

We solve the LIS problem using a dynamic programming approach. The idea is to use an array dp where dp[i] represents the length of the longest increasing subsequence ending at index i.

The steps are as follows:

Initialize a dp array of the same length as the input array with all values set to 1, since each element is a subsequence of length 1 by itself.
For each element arr[i], iterate through all previous elements arr[j] where j < i.
- If arr[j] < arr[i], then update dp[i] as dp[i] = max(dp[i], dp[j] + 1).
The final answer is the maximum value in the dp array, which represents the length of the longest increasing subsequence.

Python Program

</>

Copy

def longest_increasing_subsequence(arr):
    """
    Compute the length of the longest increasing subsequence (LIS) in an array.
    
    Parameters:
    arr (list): List of integers.
    
    Returns:
    int: Length of the longest increasing subsequence.
    """
    if not arr:
        return 0
    
    # Initialize the dp array where each element starts with a subsequence length of 1.
    n = len(arr)
    dp = [1] * n
    
    # Build the dp table
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    # The length of the longest increasing subsequence is the maximum value in dp.
    return max(dp)

# Test examples
print("Example 1:")
arr1 = [10, 9, 2, 5, 3, 7, 101, 18]
print("Input:", arr1)
print("Length of LIS:", longest_increasing_subsequence(arr1))
# Expected Output: 4, as the longest increasing subsequence is [2, 3, 7, 101]

print("\nExample 2:")
arr2 = [0, 1, 0, 3, 2, 3]
print("Input:", arr2)
print("Length of LIS:", longest_increasing_subsequence(arr2))
# Expected Output: 4, as one of the longest increasing subsequences is [0, 1, 2, 3]

Explanation: The function longest_increasing_subsequence initializes a dp array where each index starts with a value of 1. For each element in the array, the nested loop checks all previous elements and updates the dp value if a longer increasing subsequence ending at that element is found. Finally, the maximum value in the dp array represents the length of the longest increasing subsequence.

Conclusion

In this tutorial, we tackled the Longest Increasing Subsequence problem using dynamic programming. We discussed the problem statement, walked through sample inputs and outputs, and presented a step-by-step solution using a DP approach. This method efficiently computes the length of the longest increasing subsequence in O(n²) time complexity, which is suitable for many practical scenarios.

TutorialKart

Python – Longest Increasing Subsequence