Longest Bitonic Subsequence | (DP-46)

Problem Statement:

Longest Bitonic Subsequence

Prerequisite: Longest increasing subsequence, Printing Longest Increasing subsequence

Problem Link:

Given an array, ‘Arr’ of length ‘n’, find the longest bitonic subsequence.

Problem Statement:

Let us first understand what a bitonic subsequence means.

A bitonic subsequence is a subsequence of an array in which the elements can be any of these three:

First, increase till a point and then decrease.
Goes on increasing (Longest increasing subsequence)
Goes on decreasing (Longest decreasing subsequence)

Bitonic subsequence for the below example is:

Similarly, a subsequence having the elements in either increasing or decreasing order only also counts as a bitonic subsequence. For example:

We need to return the length of the longest bitonic subsequence as our answer.

Solution

Intuition:

The length of the increasing and then decreasing subsequence gives us the hint to think in terms of the longest increasing subsequence (LIS). Now let us revise the approach for finding the LIS as discussed in Printing Longest Increasing subsequence. Readers are highly advised to understand that approach first. In that solution, we write two nested loops to get a dp array whose maximum element gives us the length of the LIS as shown below:

Now, what does this dp[i] represent? It represents the LIS in the array ‘arr’ from index 0 to index i in the array ending with element arr[i]. Therefore the maximum value of dp[i] gives us the LIS of the array.

Now, after understanding the approach to finding the LIS let us revisit the problem of the longest bitonic subsequence and how it is linked with the problem of LIS.

The below figure breaks general bitonic subsequence into two parts:

As we can see in the second part of the bitonic subsequence, the decreasing part, LDS from index i to index n-1 can also be thought of in terms of LIS from index n-1 to index i. Therefore we can compute this two LIS separately to determine the length of the bitonic subsequence:

Now with these two separate lengths of LIS, we can calculate the length of the longest bitonic subsequence for each index i. Here index i is acting as the pivot point of the points. Therefore the length of the longest bitonic subsequence at pivot [ i ] will be dp1[i] + dp2[i] -1. (Note that we are counting the element at index i twice in both the parts so we need to subtract 1 from the final answer). We will return the maximum value of this addition as the final answer as the length of the longest bitonic subsequence.

Therefore we will return the max in ans array (6) as the final answer.

Approach:

The algorithm approach is stated as follows:

Using the approach of the article Printing Longest Increasing subsequence, find the dp1[ ] array, where dp1[i] gives us the length of the LIS from index 0 to index i.
Modifying the approach slightly, find the dp2[ ] array, where dp2[i] gives us the length of the LIS from index n-1 to index i. To find this opposite direction LIS simply reverses the direction of variables in the nested loops (see the code).
At last return the answer (the length of the longest bitonic subsequence) as the maximum value of dp1[i] – dp2[i] -1.

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std;

// Function to find the length of the longest bitonic subsequence
int longestBitonicSequence(vector<int>& arr, int n) {
    // Initialize two arrays to store the increasing and decreasing subsequences
    vector<int> dp1(n, 1); // dp1[i] stores the length of the longest increasing subsequence ending at arr[i]
    vector<int> dp2(n, 1); // dp2[i] stores the length of the longest decreasing subsequence ending at arr[i]

    // Calculate the longest increasing subsequence
    for (int i = 0; i < n; i++) {
        for (int prev_index = 0; prev_index < i; prev_index++) {
            if (arr[prev_index] < arr[i]) {
                dp1[i] = max(dp1[i], 1 + dp1[prev_index]);
            }
        }
    }

    // Reverse the direction of nested loops to calculate the longest decreasing subsequence
    for (int i = n - 1; i >= 0; i--) {
        for (int prev_index = n - 1; prev_index > i; prev_index--) {
            if (arr[prev_index] < arr[i]) {
                dp2[i] = max(dp2[i], 1 + dp2[prev_index]);
            }
        }
    }

    int maxi = -1;

    // Find the maximum length of the bitonic subsequence
    for (int i = 0; i < n; i++) {
        maxi = max(maxi, dp1[i] + dp2[i] - 1);
    }

    return maxi;
}

int main() {
    vector<int> arr = {1, 11, 2, 10, 4, 5, 2, 1};
    int n = arr.size();

    cout << "The length of the longest bitonic subsequence is " << longestBitonicSequence(arr, n) << endl;

    return 0;
}

Output:

The length of the longest bitonic subsequence is 6

Time Complexity: O(N*N)

Reason: There are two nested loops that are run twice.

Space Complexity: O(N)

Reason: We are only using two rows of size n.

Java Code

import java.util.*;

class TUF {
    // Function to find the length of the longest bitonic subsequence
    static int longestBitonicSequence(int[] arr, int n) {
        // Arrays to store lengths of increasing and decreasing subsequences
        int[] dp1 = new int[n];
        int[] dp2 = new int[n];

        // Initialize both arrays with 1, as each element itself is a subsequence of length 1
        Arrays.fill(dp1, 1);
        Arrays.fill(dp2, 1);

        // Calculate the lengths of increasing subsequences
        for (int i = 0; i < n; i++) {
            for (int prevIndex = 0; prevIndex < i; prevIndex++) {
                if (arr[prevIndex] < arr[i]) {
                    dp1[i] = Math.max(dp1[i], 1 + dp1[prevIndex]);
                }
            }
        }

        // Reverse the direction of nested loops and calculate the lengths of decreasing subsequences
        for (int i = n - 1; i >= 0; i--) {
            for (int prevIndex = n - 1; prevIndex > i; prevIndex--) {
                if (arr[prevIndex] < arr[i]) {
                    dp2[i] = Math.max(dp2[i], 1 + dp2[prevIndex]);
                }
            }
        }

        int maxi = -1;

        // Calculate the length of the longest bitonic subsequence
        for (int i = 0; i < n; i++) {
            maxi = Math.max(maxi, dp1[i] + dp2[i] - 1);
        }

        return maxi;
    }

    public static void main(String[] args) {
        int arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
        int n = arr.length;

        System.out.println("The length of the longest bitonic subsequence is " +
                longestBitonicSequence(arr, n));
    }
}

Output:

The length of the longest bitonic subsequence is 6

Time Complexity: O(N*N)

Reason: There are two nested loops that are run twice.

Space Complexity: O(N)

Reason: We are only using two rows of size n.

Python Code

def longest_bitonic_sequence(arr):
    n = len(arr)

    # Initialize two dynamic programming lists for increasing and decreasing subsequences
    dp1 = [1] * n
    dp2 = [1] * n

    # Calculate the length of the longest increasing subsequence
    for i in range(n):
        for prev_index in range(i):
            if arr[prev_index] < arr[i]:
                dp1[i] = max(dp1[i], 1 + dp1[prev_index])

    # Reverse the direction of nested loops to calculate the length of the longest decreasing subsequence
    for i in range(n - 1, -1, -1):
        for prev_index in range(n - 1, i, -1):
            if arr[prev_index] < arr[i]:
                dp2[i] = max(dp2[i], 1 + dp2[prev_index])

    maxi = -1

    # Find the maximum length of bitonic subsequence by combining increasing and decreasing lengths
    for i in range(n):
        maxi = max(maxi, dp1[i] + dp2[i] - 1)

    return maxi


if __name__ == "__main__":
    arr = [1, 11, 2, 10, 4, 5, 2, 1]
    n = len(arr)

    print("The length of the longest bitonic subsequence is", longest_bitonic_sequence(arr))

Output:

The length of the longest bitonic subsequence is 6

Time Complexity: O(N*N)

Reason: There are two nested loops that are run twice.

Space Complexity: O(N)

Reason: We are only using two rows of size n.

JavaScript Code

function longestBitonicSequence(arr) {
    const n = arr.length;

    // Initialize two arrays to store increasing and decreasing subsequences
    const dp1 = new Array(n).fill(1); // dp1[i] stores the length of the longest increasing subsequence ending at index i
    const dp2 = new Array(n).fill(1); // dp2[i] stores the length of the longest decreasing subsequence starting at index i

    // Compute the longest increasing subsequence from left to right
    for (let i = 0; i < n; i++) {
        for (let prevIndex = 0; prevIndex < i; prevIndex++) {
            if (arr[prevIndex] < arr[i]) {
                dp1[i] = Math.max(dp1[i], 1 + dp1[prevIndex]);
            }
        }
    }

    // Compute the longest decreasing subsequence from right to left
    for (let i = n - 1; i >= 0; i--) {
        for (let prevIndex = n - 1; prevIndex > i; prevIndex--) {
            if (arr[prevIndex] < arr[i]) {
                dp2[i] = Math.max(dp2[i], 1 + dp2[prevIndex]);
            }
        }
    }

    let maxi = -1;

    // Calculate the length of the longest bitonic subsequence
    for (let i = 0; i < n; i++) {
        maxi = Math.max(maxi, dp1[i] + dp2[i] - 1);
    }

    return maxi;
}

// Main function
function main() {
    const arr = [1, 11, 2, 10, 4, 5, 2, 1];

    const result = longestBitonicSequence(arr);
    console.log("The length of the longest bitonic subsequence is:", result);
}

// Call the main function
main();

Output:

The length of the longest bitonic subsequence is 6

Time Complexity: O(N*N)

Reason: There are two nested loops that are run twice.

Space Complexity: O(N)

Reason: We are only using two rows of size n.

Special thanks to Anshuman Sharma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article. If you want to suggest any improvement/correction in this article please mail us at [email protected]