[Dynamic Programming] Longest Bitonic Subsequence - Medium

The Longest Bitonic Subsequence (LBS) problem is about finding the longest part of a sequence of numbers that first goes up and then goes down. We can solve this problem well using dynamic programming. We do this by splitting it into two smaller problems: the Longest Increasing Subsequence (LIS) and the Longest Decreasing Subsequence (LDS). When we combine the results of these two, we get the length of the longest bitonic subsequence.

In this article, we will look at the Longest Bitonic Subsequence in detail. We will start with a simple explanation of what the problem is. Then, we will talk about how to solve it using dynamic programming in Java, Python, and C++. We will also check how to make the solution better, look at its complexity, point out common mistakes we can make while coding, and answer some frequently asked questions.

  • Dynamic Programming Longest Bitonic Subsequence Explained
  • Understanding the Problem Statement of Longest Bitonic Subsequence
  • Dynamic Programming Approach for Longest Bitonic Subsequence in Java
  • Dynamic Programming Approach for Longest Bitonic Subsequence in Python
  • Dynamic Programming Approach for Longest Bitonic Subsequence in C++
  • Optimizing the Longest Bitonic Subsequence Solution
  • Complexity Analysis of Longest Bitonic Subsequence Algorithm
  • Common Mistakes in Implementing Longest Bitonic Subsequence
  • Frequently Asked Questions

If you want to learn more about related dynamic programming topics, you can check these articles: Dynamic Programming: Fibonacci Number, Dynamic Programming: Longest Increasing Subsequence, and Dynamic Programming: 0-1 Knapsack Problem.

Understanding the Problem Statement of Longest Bitonic Subsequence

The Longest Bitonic Subsequence (LBS) is a well-known problem in dynamic programming. A bitonic subsequence is a sequence that goes up first and then goes down. Our goal is to find out the length of the longest subsequence that is bitonic.

Problem Definition

We have an array of integers. Our task is to find the maximum length of the subsequence that meets these rules:

  1. Increasing Phase: The numbers in the subsequence must be in a strictly increasing order.
  2. Decreasing Phase: After reaching the highest point, the numbers must be in a strictly decreasing order.

Example

Let’s look at this array:

arr = [1, 11, 2, 10, 4, 5, 2, 1]
  • One longest bitonic subsequence is [1, 2, 10, 4, 2, 1] and it has length 6.
  • Another valid bitonic subsequence is [1, 11, 10, 4, 2, 1], which also has length 6.

Input and Output

  • Input: An array of integers.
  • Output: A number that shows the length of the longest bitonic subsequence.

Constraints

  • The array must have at least one element.
  • The input array can be as big as (10^3).

We can solve this problem in a good way using dynamic programming. This means we will find the longest increasing subsequence (LIS) for all the elements first. Then we will find the longest decreasing subsequence (LDS) in reverse.

For more about similar dynamic programming problems, we can check the Longest Increasing Subsequence article.

Dynamic Programming Approach for Longest Bitonic Subsequence in Java

The Longest Bitonic Subsequence (LBS) is a sequence that first goes up and then goes down. We can solve this problem using dynamic programming. We will break it into two parts: finding the Longest Increasing Subsequence (LIS) and the Longest Decreasing Subsequence (LDS).

Steps to Implement the Dynamic Programming Solution:

  1. Calculate LIS: For each number, we find the length of the longest increasing subsequence that ends with that number.
  2. Calculate LDS: For each number, we find the length of the longest decreasing subsequence that starts with that number.
  3. Combine Results: The length of the longest bitonic subsequence at each number is the sum of its LIS and LDS lengths minus one. This is to avoid counting the peak number twice.

Java Implementation:

public class LongestBitonicSubsequence {
    public static int longestBitonicSubsequence(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        // Step 1: Calculate LIS
        int[] lis = new int[n];
        for (int i = 0; i < n; i++) {
            lis[i] = 1; // Start LIS values
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }

        // Step 2: Calculate LDS
        int[] lds = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            lds[i] = 1; // Start LDS values
            for (int j = n - 1; j > i; j--) {
                if (arr[i] > arr[j] && lds[i] < lds[j] + 1) {
                    lds[i] = lds[j] + 1;
                }
            }
        }

        // Step 3: Combine LIS and LDS
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {1, 11, 2, 10, 4, 5, 2, 1};
        System.out.println("Length of Longest Bitonic Subsequence: " + longestBitonicSubsequence(arr));
    }
}

Explanation of the Code:

  • The longestBitonicSubsequence method finds the length of the longest bitonic subsequence.
  • We use two arrays lis and lds to keep the lengths of the longest increasing and decreasing subsequences.
  • We fill these arrays with nested loops based on the rules for increasing and decreasing subsequences.
  • Finally, we find the maximum length by combining values from both arrays.

Complexity Analysis:

  • Time Complexity: O(n^2). Here, n is the length of the input array.
  • Space Complexity: O(n). This is for storing the LIS and LDS arrays.

This method finds the longest bitonic subsequence using dynamic programming in Java. For more techniques on dynamic programming, we can look at other articles like Dynamic Programming - Longest Increasing Subsequence.

Dynamic Programming Approach for Longest Bitonic Subsequence in Python

To solve the Longest Bitonic Subsequence (LBS) problem with dynamic programming in Python, we can split the problem into two main parts. First, we need to find the Longest Increasing Subsequence (LIS). Second, we find the Longest Decreasing Subsequence (LDS). After that, we can calculate the LBS using these two sequences.

Steps to Implement the Dynamic Programming Approach:

  1. We compute the Longest Increasing Subsequence (LIS) for every element.
  2. We compute the Longest Decreasing Subsequence (LDS) for every element.
  3. For each element in the array, we can find the LBS as LIS[i] + LDS[i] - 1.
  4. The final answer is the biggest LBS value from all indices.

Python Code Implementation:

def longest_bitonic_subsequence(arr):
    n = len(arr)
    if n == 0:
        return 0
    
    # Step 1: Calculate LIS
    lis = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    # Step 2: Calculate LDS
    lds = [1] * n
    for i in range(n-1, -1, -1):
        for j in range(n-1, i, -1):
            if arr[i] > arr[j]:
                lds[i] = max(lds[i], lds[j] + 1)

    # Step 3: Calculate LBS
    lbs = 0
    for i in range(n):
        lbs = max(lbs, lis[i] + lds[i] - 1)

    return lbs

# Example usage
arr = [12, 4, 78, 90, 45, 23]
print("Length of Longest Bitonic Subsequence is:", longest_bitonic_subsequence(arr))

Explanation of the Code:

  • The longest_bitonic_subsequence function takes an array arr as input. It starts by making two lists, lis and lds, to keep the lengths of the longest increasing and decreasing subsequences for each index.
  • We use two loops to calculate LIS and LDS. The first loop goes through each element. The second loop checks the previous elements for LIS and the next elements for LDS.
  • At the end, we calculate the LBS by adding the values of lis and lds for each index and subtracting 1. This is to avoid counting the peak element twice.

Complexity:

  • Time Complexity: O(n^2) because we have nested loops for LIS and LDS.
  • Space Complexity: O(n) for saving the lengths of LIS and LDS.

For more reading on similar dynamic programming problems, you can check the Dynamic Programming - Longest Increasing Subsequence article.

Dynamic Programming Approach for Longest Bitonic Subsequence in C++

We will solve the Longest Bitonic Subsequence (LBS) problem using dynamic programming in C++. First, we need to know that a bitonic subsequence goes up and then goes down. We can do this in two main steps:

  1. Calculate the Longest Increasing Subsequence (LIS) for each item from the left side.
  2. Calculate the Longest Decreasing Subsequence (LDS) for each item from the right side.

After we finish both steps, we can find the LBS for each item by adding these two results together. Finally, we will take the biggest value from these combined results.

C++ Implementation

Here is a simple code for the logic we explained above in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(const vector<int>& arr) {
    int n = arr.size();
    vector<int> lis(n, 1);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }
    return lis;
}

int longestDecreasingSubsequence(const vector<int>& arr) {
    int n = arr.size();
    vector<int> lds(n, 1);
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = max(lds[i], lds[j] + 1);
            }
        }
    }
    return lds;
}

int longestBitonicSubsequence(const vector<int>& arr) {
    vector<int> lis = longestIncreasingSubsequence(arr);
    vector<int> lds = longestDecreasingSubsequence(arr);
    
    int maxLength = 0;
    for (int i = 0; i < arr.size(); i++) {
        maxLength = max(maxLength, lis[i] + lds[i] - 1);
    }
    
    return maxLength;
}

int main() {
    vector<int> arr = {1, 3, 5, 4, 7};
    int result = longestBitonicSubsequence(arr);
    cout << "Length of Longest Bitonic Subsequence: " << result << endl;
    return 0;
}

Explanation of the Code

  • Function longestIncreasingSubsequence: This function finds the length of the longest increasing subsequence for each item.
  • Function longestDecreasingSubsequence: This function finds the length of the longest decreasing subsequence for each item.
  • Function longestBitonicSubsequence: This function adds the results from LIS and LDS for each index and finds the maximum length of the bitonic subsequence.

Complexity Analysis

  • Time complexity: O(n^2), where n is the size of the input array.
  • Space complexity: O(n) for keeping LIS and LDS values.

This method uses dynamic programming well to solve the Longest Bitonic Subsequence problem in C++. If you want to learn more about dynamic programming, you can check out Longest Increasing Subsequence.

Optimizing the Longest Bitonic Subsequence Solution

To make the solution for finding the Longest Bitonic Subsequence (LBS) better, we can use the ideas from the Longest Increasing Subsequence (LIS) and the Longest Decreasing Subsequence (LDS). We can get the LBS from these two parts.

Steps to Optimize

  1. Calculate LIS: We find the longest increasing subsequence for each index.
  2. Calculate LDS: We find the longest decreasing subsequence for each index.
  3. Combine Results: The length of the longest bitonic subsequence at each index is the sum of LIS and LDS minus one. This is to make sure we do not count the peak element twice.

Time Complexity

The improved algorithm works in (O(n^2)) because of the nested loops to calculate LIS and LDS. We can make it faster to (O(n n)) using binary search, but we will use the (O(n^2)) method for simplicity here.

Java Implementation

public class LongestBitonicSubsequence {
    public static int longestBitonicSubsequence(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        int[] lis = new int[n];
        int[] lds = new int[n];

        // Compute LIS values
        for (int i = 0; i < n; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // Compute LDS values
        for (int i = n - 1; i >= 0; i--) {
            lds[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (arr[i] > arr[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        // Combine LIS and LDS
        int maxLBS = 0;
        for (int i = 0; i < n; i++) {
            maxLBS = Math.max(maxLBS, lis[i] + lds[i] - 1);
        }

        return maxLBS;
    }

    public static void main(String[] args) {
        int[] arr = {1, 11, 2, 10, 4, 5, 2, 1};
        System.out.println("Length of Longest Bitonic Subsequence: " + longestBitonicSubsequence(arr));
    }
}

Python Implementation

def longest_bitonic_subsequence(arr):
    n = len(arr)
    if n == 0:
        return 0

    lis = [1] * n
    lds = [1] * n

    # Compute LIS values
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    # Compute LDS values
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, i, -1):
            if arr[i] > arr[j]:
                lds[i] = max(lds[i], lds[j] + 1)

    # Combine LIS and LDS
    max_lbs = 0
    for i in range(n):
        max_lbs = max(max_lbs, lis[i] + lds[i] - 1)

    return max_lbs

# Example Usage
arr = [1, 11, 2, 10, 4, 5, 2, 1]
print("Length of Longest Bitonic Subsequence:", longest_bitonic_subsequence(arr))

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestBitonicSubsequence(vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return 0;

    vector<int> lis(n, 1);
    vector<int> lds(n, 1);

    // Compute LIS values
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                lis[i] = max(lis[i], lis[j] + 1);
            }
        }
    }

    // Compute LDS values
    for (int i = n - 1; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = max(lds[i], lds[j] + 1);
            }
        }
    }

    // Combine LIS and LDS
    int maxLBS = 0;
    for (int i = 0; i < n; i++) {
        maxLBS = max(maxLBS, lis[i] + lds[i] - 1);
    }

    return maxLBS;
}

int main() {
    vector<int> arr = {1, 11, 2, 10, 4, 5, 2, 1};
    cout << "Length of Longest Bitonic Subsequence: " << longestBitonicSubsequence(arr) << endl;
    return 0;
}

This method helps to find the longest bitonic subsequence by mixing results from longest increasing and decreasing subsequences. If you want to learn more about dynamic programming, you can look at other algorithms like Longest Increasing Subsequence.

Complexity Analysis of Longest Bitonic Subsequence Algorithm

We can look at the Longest Bitonic Subsequence (LBS) problem by checking its time and space complexity when we use dynamic programming. The LBS is a subsequence that first goes up and then goes down.

Time Complexity

  1. Dynamic Programming Approach:
    • The algorithm has two main steps.
      • First, we find the Longest Increasing Subsequence (LIS) for each element from the left.
      • Then, we find the Longest Decreasing Subsequence (LDS) for each element from the right.
    • Each LIS and LDS calculation takes (O(n^2)) time. Here, (n) is the length of the input sequence.
    • So, the overall time complexity for the LBS algorithm is: [ O(n^2) ]
  2. Optimized Approach (Using Binary Search):
    • If we use binary search to find the LIS and LDS, we can make the time for each (O(n n)).
    • So, with this method, the overall time complexity can be better to: [ O(n n) ]
    • We do this by keeping an extra array. This array helps us track the longest subsequence better.

Space Complexity

  1. Dynamic Programming Approach:
    • The space complexity mostly comes from storing the results of LIS and LDS calculations.
    • We need two extra arrays to keep track of the lengths of the sequences. Each array has size (n): [ O(n) ]
    • Therefore, the total space complexity for the normal dynamic programming method is: [ O(n) ]
  2. Optimized Approach:
    • If we use the better method with binary search, the space complexity can still be (O(n)) for storing the lengths of LIS and LDS.
    • The extra array for binary search can also be small. This leads to: [ O(n) ]

The complexity analysis shows that we can solve the LBS algorithm in (O(n^2)), but we can also make it faster to (O(n n)) with the right method. We keep the space complexity linear. This makes dynamic programming a good way to solve the Longest Bitonic Subsequence problem well.

Common Mistakes in Implementing Longest Bitonic Subsequence

When we implement the Longest Bitonic Subsequence (LBS) algorithm, we often make some common mistakes. Knowing these mistakes can help us make our solution better and more correct.

  1. Incorrect Calculation of Increasing and Decreasing Subsequences:
    • We must make sure we calculate both the increasing and decreasing subsequences right. Sometimes, we forget about boundary conditions or do not reset indices when we switch from increasing to decreasing parts.
  2. Improper Use of Dynamic Programming Arrays:
    • Many times, we do not start the dynamic programming (DP) arrays correctly. Both the increasing and decreasing arrays should start at 1 because the smallest length of any subsequence is 1. This means just the single element.
  3. Missing Edge Cases:
    • We need to handle edge cases like sequences with all same elements or sequences that only go up or down. If we do not think about these, we can get wrong answers.
  4. Inefficient Time Complexity:
    • Some of us may use nested loops without making the DP filling process better. The time we expect is O(n^2), but sometimes we make it O(n^3) by putting loops in the wrong place.
  5. Confusing the Length of the Bitonic Subsequence:
    • We must remember that the length of the longest bitonic subsequence comes from adding the lengths of the longest increasing and longest decreasing subsequences. If we forget about the peak element, which we count twice, we can get incorrect results.
  6. Not Handling Input Validations:
    • We often forget to check the input before we start. The algorithm should work well when the input array is empty or has only one element.
  7. Verbose Code Leading to Logic Errors:
    • If we write complicated code, it can lead to logic mistakes. Keeping our code simple and clear will help keep the algorithm correct.

Here’s a sample implementation of the Longest Bitonic Subsequence in Python to show a good structure:

def longest_bitonic_subsequence(arr):
    n = len(arr)
    if n == 0:
        return 0
    
    # Initialize DP arrays
    increasing = [1] * n
    decreasing = [1] * n

    # Fill increasing subsequence DP array
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                increasing[i] = max(increasing[i], increasing[j] + 1)

    # Fill decreasing subsequence DP array
    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if arr[i] > arr[j]:
                decreasing[i] = max(decreasing[i], decreasing[j] + 1)

    # Find maximum value of LBS
    max_length = 0
    for i in range(n):
        max_length = max(max_length, increasing[i] + decreasing[i] - 1)

    return max_length

By avoiding these mistakes and following some best practices, we can make a stronger and faster Longest Bitonic Subsequence algorithm. For more reading about dynamic programming methods and other problems, check out articles like Dynamic Programming - Longest Increasing Subsequence.

Frequently Asked Questions

What is the definition of the Longest Bitonic Subsequence?

The Longest Bitonic Subsequence (LBS) is a special type of subsequence. It starts by increasing and then it decreases. This is a common problem in dynamic programming. The goal is to find the longest length of this subsequence. We need to understand bitonic sequences well to use dynamic programming methods effectively.

How can I implement the Longest Bitonic Subsequence algorithm in Java?

To implement the Longest Bitonic Subsequence in Java, we usually make two arrays. One array is for the longest increasing subsequence (LIS) and the other is for the longest decreasing subsequence (LDS) for each element. Next, we go through the sequence to find the values. Finally, we find the maximum value by combining LIS and LDS at each index. You can see our guide for the Dynamic Programming Approach for Longest Bitonic Subsequence in Java.

What are the time and space complexities of the Longest Bitonic Subsequence algorithm?

The time complexity for the Longest Bitonic Subsequence algorithm using dynamic programming is O(n^2). Here, n is the length of the input sequence. The space complexity is O(n) because we use extra arrays to keep intermediate results. We can try to reduce space complexity if we want.

Can you explain the difference between Longest Increasing Subsequence and Longest Bitonic Subsequence?

The Longest Increasing Subsequence (LIS) has elements that only increase. The Longest Bitonic Subsequence allows for an initial increase followed by a decrease. So, an LBS has a LIS and then a LDS. This makes it a bit more complex and suitable for dynamic programming. For more details, check out our article on the Dynamic Programming Longest Increasing Subsequence.

What are some common mistakes to avoid when implementing the Longest Bitonic Subsequence?

Common mistakes in implementing the Longest Bitonic Subsequence include not calculating the LIS and LDS arrays correctly. We might also forget edge cases, like single-element arrays. Not combining the results properly is another mistake. It is very important to manage your indices well and to consider all subsequences. For more tips, look at the section on Common Mistakes in Implementing Longest Bitonic Subsequence.