Finding the Longest Increasing Subsequence in Python
The Longest Increasing Subsequence (LIS) problem involves finding the longest subsequence in a sequence of numbers where the elements of the subsequence are in strictly increasing order. An efficient solution can be achieved using dynamic programming.
Below is a Python function that implements this approach:
def longest_increasing_subsequence(sequence):
if not sequence:
return []
# Initialize an array to store the length of the longest
# increasing subsequence at each index
n = len(sequence)
dp = [1] * n # Each element is an LIS of at least 1 (itself)
# This array keeps track of the indices of the previous elements in the LIS
previous_index = [-1] * n
# Fill the dp array and previous_index array
for i in range(1, n):
for j in range(i):
if sequence[i] > sequence[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
previous_index[i] = j
# Find the index of the maximum length of LIS
max_length = max(dp)
index = dp.index(max_length)
# Reconstruct the longest increasing subsequence
lis = []
while index != -1:
lis.append(sequence[index])
index = previous_index[index]
# The subsequence is constructed in reverse order, so we reverse it
lis.reverse()
return lis
# Example usage
sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print("Longest Increasing Subsequence:", longest_increasing_subsequence(sequence))
Explanation of the Code
1. Initialization: The function initializes a list dp to store the lengths of the longest increasing subsequences that end at each position in the input list. Each position starts with the value 1 because each individual element is an increasing subsequence by itself.
2. Dynamic Programming Approach: Nested loops are utilized to compare each element with previous elements. If an element is greater than a previous element and can extend the increasing subsequence ending at that previous element (dp[i] < dp[j] + 1), the dp and previous_index lists are updated accordingly.
3. Finding the Maximum Length: After filling the dp, the maximum value is obtained to determine the length of the longest increasing subsequence. The index of this maximum length is used to reconstruct the subsequence.
4. Reconstructing the LIS: The subsequence is built by tracing back using the previous_index array, which stores the index of the last element in the subsequence.
5. Return Value: Finally, the constructed subsequence is reversed (since it was built backwards) and returned.
Complexity
The time complexity of this solution is \(O(n^2)\), where \(n\) is the number of elements in the input list. Space complexity is \(O(n)\) due to the additional storage for the dp and previous_index arrays.
Example
For the input list [10, 22, 9, 33, 21, 50, 41, 60, 80], the function will output the longest increasing subsequence, which might be [10, 22, 33, 50, 60, 80].