Day 35

Day 35: Longest Increasing Subsequence

Advanced 13 min

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# Example usage
19arr = [ …

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!

Solution#

The worked solution is a lifetime-access perk. Unlock all 60 solutions. Already purchased? Log in to view it.

Show the solution

Exercise 2: find the Longest Bitonic Subsequence (first strictly increasing, then strictly decreasing).

 1def longest_bitonic_subsequence(arr):
 2    n = len(arr)
 3    if n == 0:
 4        return 0
 5    # lis[i]: longest increasing subsequence ending at i
 6    lis = [1] * n
 7    for i in range(1, n):
 8        for j in range(i):
 9            if arr[j] < arr[i]:
10                lis[i] = max(lis[i], lis[j] + 1)
11    # lds[i]: longest decreasing subsequence starting at i
12    lds = [1] * n
13    for i in range(n - 2, -1, -1):
14        for j in range(i + 1, n):
15            if arr[j] < arr[i]:
16                lds[i] = max(lds[i], lds[j] + 1)
17    # each peak i is counted in both, so subtract 1
18    return max(lis[i] + lds[i] - 1 for i in range(n))
19
20# Example usage
21arr = [1, 11, 2, 10, 4, 5, 2, 1]
22print(f"Length of longest bitonic subsequence: {longest_bitonic_subsequence(arr)}")  # 6

A bitonic subsequence has a single peak. We compute, for every index, the longest increasing subsequence ending there (lis) and the longest decreasing subsequence starting there (lds). If we treat index i as the peak, the total length is lis[i] + lds[i] - 1 (the peak is shared, so subtract one). The answer is the maximum over all peaks. Both passes are the O(n^2) LIS-style DP. Time complexity is O(n^2) and space complexity is O(n).

Keep your momentum going

Create a free account to unlock the full lesson, all 60 days, and track your progress as you go.