Day 35

Day 35: Longest Increasing Subsequence

35/60 Days

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) #

What is the Longest Increasing Subsequence? #

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!

Longest Increasing Subsequence (LIS) #

What is the Longest Increasing Subsequence? #

Naive Recursive Approach #

Longest Increasing Subsequence (LIS) #

What is the Longest Increasing Subsequence? #

Naive Recursive Approach #

Dynamic Programming Approach #

Top-Down Approach (Memoization) #

Bottom-Up Approach (Tabulation) #

Optimized Solution using Binary Search #

Printing the Longest Increasing Subsequence #

Applications of LIS #

Exercise #

Summary #

Continue Reading

Re-enter Password

Confirm Action