Longest Increasing Subsequence (LIS)
Welcome to Day 35 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Longest Increasing Subsequence (LIS) problem, a classic dynamic programming problem with applications in various fields.
What is the Longest Increasing Subsequence?
The Longest Increasing Subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.
For example, the LIS of [10, 22, 9, 33, 21, 50, 41, 60, 80] is [10, 22, 33, 50, 60, 80] of length 6.
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def lis_naive(arr):
2 n = len(arr)
3
4 def lis_helper(i, prev):
5 if i == n:
6 return 0
7
8 include = 0
9 if arr[i] > prev:
10 include = 1 + lis_helper(i + 1, arr[i])
11
12 exclude = lis_helper(i + 1, prev)
13
14 return max(include, exclude)
15
16 return lis_helper(0, float('-inf'))
17
18# …
Longest Increasing Subsequence (LIS)
Welcome to Day 35 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Longest Increasing Subsequence (LIS) problem, a classic dynamic programming problem with applications in various fields.
What is the Longest Increasing Subsequence?
The Longest Increasing Subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.
For example, the LIS of [10, 22, 9, 33, 21, 50, 41, 60, 80] is [10, 22, 33, 50, 60, 80] of length 6.
Naive Recursive Approach
Let’s start with a naive recursive implementation:
1def lis_naive(arr):
2 n = len(arr)
3
4 def lis_helper(i, prev):
5 if i == n:
6 return 0
7
8 include = 0
9 if arr[i] > prev:
10 include = 1 + lis_helper(i + 1, arr[i])
11
12 exclude = lis_helper(i + 1, prev)
13
14 return max(include, exclude)
15
16 return lis_helper(0, float('-inf'))
17
18# Example usage
19arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
20print(f"Length of LIS is {lis_naive(arr)}")
This approach has a time complexity of O(2^n), making it inefficient for larger inputs.
Dynamic Programming Approach
We can significantly improve the efficiency using Dynamic Programming.
Top-Down Approach (Memoization)
1def lis_memo(arr):
2 n = len(arr)
3 memo = {}
4
5 def lis_helper(i, prev_index):
6 if i == n:
7 return 0
8
9 if (i, prev_index) in memo:
10 return memo[(i, prev_index)]
11
12 include = 0
13 if prev_index == -1 or arr[i] > arr[prev_index]:
14 include = 1 + lis_helper(i + 1, i)
15
16 exclude = lis_helper(i + 1, prev_index)
17
18 memo[(i, prev_index)] = max(include, exclude)
19 return memo[(i, prev_index)]
20
21 return lis_helper(0, -1)
22
23# Example usage
24arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
25print(f"Length of LIS is {lis_memo(arr)}")
Bottom-Up Approach (Tabulation)
1def lis_tab(arr):
2 n = len(arr)
3 dp = [1] * n
4
5 for i in range(1, n):
6 for j in range(i):
7 if arr[i] > arr[j]:
8 dp[i] = max(dp[i], dp[j] + 1)
9
10 return max(dp)
11
12# Example usage
13arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
14print(f"Length of LIS is {lis_tab(arr)}")
The Dynamic Programming approaches have a time complexity of O(n^2) and a space complexity of O(n).
Optimized Solution using Binary Search
We can further optimize the solution to achieve O(n log n) time complexity:
1def lis_optimized(arr):
2 n = len(arr)
3 if n == 0:
4 return 0
5
6 tail = [0] * n
7 length = 1
8 tail[0] = arr[0]
9
10 for i in range(1, n):
11 if arr[i] < tail[0]:
12 tail[0] = arr[i]
13 elif arr[i] > tail[length-1]:
14 tail[length] = arr[i]
15 length += 1
16 else:
17 tail[binary_search(tail, 0, length-1, arr[i])] = arr[i]
18
19 return length
20
21def binary_search(tail, low, high, key):
22 while high > low:
23 mid = (low + high) // 2
24 if tail[mid] >= key:
25 high = mid
26 else:
27 low = mid + 1
28 return high
29
30# Example usage
31arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
32print(f"Length of LIS is {lis_optimized(arr)}")
This optimized version has a time complexity of O(n log n) and a space complexity of O(n).
Printing the Longest Increasing Subsequence
We can modify our solution to also print the LIS:
1def lis_with_sequence(arr):
2 n = len(arr)
3 dp = [1] * n
4 prev = [-1] * n
5
6 for i in range(1, n):
7 for j in range(i):
8 if arr[i] > arr[j] and dp[i] < dp[j] + 1:
9 dp[i] = dp[j] + 1
10 prev[i] = j
11
12 # Find the index of the maximum value in dp
13 max_length = max(dp)
14 max_index = dp.index(max_length)
15
16 # Reconstruct the sequence
17 sequence = []
18 while max_index != -1:
19 sequence.append(arr[max_index])
20 max_index = prev[max_index]
21
22 return max_length, sequence[::-1]
23
24# Example usage
25arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
26length, sequence = lis_with_sequence(arr)
27print(f"Length of LIS is {length}")
28print(f"LIS is {sequence}")
Applications of LIS
- Analyzing sequence data in bioinformatics
- Predicting stock market trends
- Text compression algorithms
- Optimization in computer graphics (e.g., optimal triangulation)
- Finding the longest chain of pairs in array of pairs
Exercise
Implement a function to find the Longest Decreasing Subsequence.
Modify the LIS algorithm to find the Longest Bitonic Subsequence (a subsequence that first increases, then decreases).
Implement a function to find the Longest Common Increasing Subsequence of two arrays.
Summary
Today, we explored the Longest Increasing Subsequence problem, a classic example of dynamic programming. We implemented various approaches, from naive recursion to optimized dynamic programming solutions, and even a version that provides the actual subsequence.
Understanding the LIS problem and its solutions provides valuable insights into dynamic programming techniques and their applications in sequence analysis and optimization problems.
Tomorrow, we’ll dive into another fundamental algorithm: Dijkstra’s Shortest Path Algorithm. Stay tuned!