Printing Longest Bitonic Subsequence

Table of Contents#

1. Understanding Bitonic Subsequences
2. Algorithm for Finding the Longest Bitonic Subsequence
   • Step 1: Find the Longest Increasing Subsequence (LIS)
   • Step 2: Find the Longest Decreasing Subsequence (LDS)
   • Step 3: Calculate the Longest Bitonic Subsequence
3. Printing the Longest Bitonic Subsequence
   • Backtracking Approach
4. Example Usage
5. Complexity Analysis
6. Common Practices and Best Practices
7. Conclusion
8. References

1. Understanding Bitonic Subsequences#

A bitonic sequence is a sequence of numbers where the elements initially increase and then decrease. For example, the sequence [1, 3, 5, 4, 2] is a bitonic sequence because it first increases from 1 to 5 and then decreases from 5 to 2.

A subsequence of a given sequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. For instance, if the original sequence is [1, 2, 3, 4, 5], then [1, 3, 5] is a subsequence.

The Longest Bitonic Subsequence (LBS) of a given sequence is the longest subsequence that is bitonic.

2. Algorithm for Finding the Longest Bitonic Subsequence#

Step 1: Find the Longest Increasing Subsequence (LIS)#

The first step in finding the LBS is to find the Longest Increasing Subsequence (LIS) for each element in the given sequence. We can use the dynamic programming approach to solve the LIS problem.

Let arr[] be the given sequence of length n. We create an array lis[] of the same length, where lis[i] stores the length of the LIS ending at index i.

def lis(arr):
    n = len(arr)
    lis = [1] * n
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return lis

Step 2: Find the Longest Decreasing Subsequence (LDS)#

The next step is to find the Longest Decreasing Subsequence (LDS) for each element in the given sequence. We can do this by reversing the given sequence and then finding the LIS of the reversed sequence.

def lds(arr):
    n = len(arr)
    lds = [1] * n
    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if arr[i] > arr[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1
    return lds

Step 3: Calculate the Longest Bitonic Subsequence#

The length of the LBS at each index i is the sum of the length of the LIS ending at index i and the length of the LDS starting at index i, minus 1 (to avoid double - counting the element at index i).

def lbs_length(arr):
    lis_arr = lis(arr)
    lds_arr = lds(arr)
    max_length = 0
    for i in range(len(arr)):
        max_length = max(max_length, lis_arr[i] + lds_arr[i] - 1)
    return max_length

3. Printing the Longest Bitonic Subsequence#

Backtracking Approach#

To print the Longest Bitonic Subsequence, we can use a backtracking approach. We first find the index k where the length of the LBS is maximum. Then, we backtrack through the LIS and LDS arrays to print the increasing and decreasing parts of the subsequence respectively.

def print_lbs(arr):
    n = len(arr)
    lis_arr = lis(arr)
    lds_arr = lds(arr)
    max_length = 0
    index = 0
    for i in range(n):
        current_length = lis_arr[i] + lds_arr[i] - 1
        if current_length > max_length:
            max_length = current_length
            index = i
 
    # Print the increasing part
    increasing = []
    i = index
    length = lis_arr[index]
    while i >= 0 and length > 0:
        if lis_arr[i] == length:
            increasing.append(arr[i])
            length -= 1
        i -= 1
    increasing.reverse()
 
    # Print the decreasing part
    decreasing = []
    i = index
    length = lds_arr[index] - 1
    while i < n and length > 0:
        if lds_arr[i] == length + 1:
            decreasing.append(arr[i])
            length -= 1
        i += 1
 
    lbs = increasing + decreasing
    return lbs

4. Example Usage#

Let's use the above functions to find and print the Longest Bitonic Subsequence of a given sequence.

arr = [1, 11, 2, 10, 4, 5, 2, 1]
print("Longest Bitonic Subsequence length:", lbs_length(arr))
print("Longest Bitonic Subsequence:", print_lbs(arr))

In this example, the output will show the length of the LBS and the actual LBS itself.

5. Complexity Analysis#

• Time Complexity: The time complexity of finding the LIS and LDS is $O(n^2)$ each, where n is the length of the input sequence. The overall time complexity of finding and printing the LBS is $O(n^2)$ due to the nested loops in the LIS and LDS algorithms.
• Space Complexity: The space complexity is $O(n)$ because we use two additional arrays lis[] and lds[] of length n to store the lengths of the LIS and LDS respectively.

6. Common Practices and Best Practices#

• Dynamic Programming: Using dynamic programming to solve the LIS and LDS problems is a common and efficient approach. It avoids redundant calculations by storing the results of subproblems in arrays.
• Backtracking: When printing the actual subsequence, backtracking is a useful technique. It allows us to reconstruct the subsequence from the lengths stored in the lis[] and lds[] arrays.
• Code Modularity: Breaking the code into smaller functions for finding the LIS, LDS, and the LBS makes the code more readable and maintainable.

7. Conclusion#

The problem of finding and printing the Longest Bitonic Subsequence is a classic problem in computer science. By using dynamic programming and backtracking techniques, we can efficiently solve this problem. The time complexity of the algorithm is $O(n^2)$, which is reasonable for moderate - sized input sequences. The code can be further optimized and extended depending on the specific requirements of the application.

8. References#

• Cormen, Thomas H., et al. Introduction to Algorithms. MIT press, 2009.
• GeeksforGeeks. "Longest Bitonic Subsequence." https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/