Solve the Longest Bitonic Subsequence problem using dynamic programming.?

The Longest Bitonic Subsequence problem asks us to find the longest subsequence of an input sequence that first increases and then decreases.

Dynamic programming is a good fit for this problem since we can break it down into smaller subproblems and use the solutions to these subproblems to solve the overall problem.

We can approach this problem using two dynamic programming arrays - one to store the longest increasing subsequence ending at each index in the input sequence, and another to store the longest decreasing subsequence starting at each index in the input sequence.

Let’s call the input sequence ‘arr‘ of length ‘n‘. We can initialize both arrays to have a length of ‘n‘ and all values to be 1, since the longest increasing/decreasing subsequence at any index will always be at least 1 (the element itself).

To compute the longest increasing subsequence for each index in ‘arr‘, we can iterate through the array from left to right and compare the value at each index to all the values to its left. If ‘arr[i] > arr[j]‘ (where ‘j‘ is any index to the left of ‘i‘), we can update the longest increasing subsequence ending at ‘arr[i]‘ to be the maximum value of ‘lis[j] + 1‘ (the longest increasing subsequence ending at ‘arr[j]‘ plus one for ‘arr[i]‘ itself) and the current value of ‘lis[i]‘. Essentially, we are asking - if I include the element at index ‘i‘, what is the longest increasing subsequence that I can form up to this point?

Similarly, to compute the longest decreasing subsequence for each index in ‘arr‘, we can iterate through the array from right to left and compare the value at each index to all the values to its right. If ‘arr[i] > arr[j]‘ (where ‘j‘ is any index to the right of ‘i‘), we can update the longest decreasing subsequence starting at ‘arr[i]‘ to be the maximum value of ‘lds[j] + 1‘ (the longest decreasing subsequence starting at ‘arr[j]‘ plus one for ‘arr[i]‘ itself) and the current value of ‘lds[i]‘. Essentially, we are asking - if I include the element at index ‘i‘, what is the longest decreasing subsequence that I can form starting from this point?

Finally, we can compute the longest bitonic subsequence by iterating through ‘arr‘ and finding the maximum value of ‘lis[i] + lds[i] - 1‘. Note that we subtract one since we are double counting the value at index ‘i‘.

Here is the Java code implementation of the Longest Bitonic Subsequence problem using dynamic programming:

public static int longestBitonicSubsequence(int[] arr) {
    int n = arr.length;
    int[] lis = new int[n];
    int[] lds = new int[n];

    // initialize both arrays to have a length of n and all values to be 1
    Arrays.fill(lis, 1);
    Arrays.fill(lds, 1);

    // compute the longest increasing subsequence for each index in arr
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                lis[i] = Math.max(lis[i], lis[j] + 1);
            }
        }
    }

    // compute the longest decreasing subsequence for each index in arr
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = Math.max(lds[i], lds[j] + 1);
            }
        }
    }

    int maxBitonicLength = 0;
    // compute the longest bitonic subsequence by finding the maximum value of lis[i] + lds[i] - 1
    for (int i = 0; i < n; i++) {
        maxBitonicLength = Math.max(maxBitonicLength, lis[i] + lds[i] - 1);
    }

    return maxBitonicLength;
}

Let’s say we have ‘arr = 1, 11, 2, 10, 4, 5, 2, 1‘. This sequence has a longest bitonic subsequence of length 6, which is 1, 2, 10, 5, 2, 1. We can verify that this code returns the correct answer:

int[] arr = {1, 11, 2, 10, 4, 5, 2, 1};
int longestBitonicLength = longestBitonicSubsequence(arr);
System.out.println(longestBitonicLength); // Output: 6