LongestBitonicSubsequence.java

import java.util.*;

public class LongestBitonicSubsequence {

    // Function to compute Longest Increasing Subsequence (LIS) for each element
    public static int[] computeLIS(int[] arr) {
        int n = arr.length;
        int[] lis = new int[n];
        Arrays.fill(lis, 1); // Minimum length of LIS is 1 for each element

        // Compute LIS values from left to right
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }
        return lis;
    }

    // Function to compute Longest Decreasing Subsequence (LDS) for each element
    public static int[] computeLDS(int[] arr) {
        int n = arr.length;
        int[] lds = new int[n];
        Arrays.fill(lds, 1); // Minimum length of LDS is 1 for each element

        // Compute LDS values from right to left
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (arr[i] > arr[j] && lds[i] < lds[j] + 1) {
                    lds[i] = lds[j] + 1;
                }
            }
        }
        return lds;
    }

    // Function to compute the length of the Longest Bitonic Subsequence
    public static int longestBitonicSubsequence(int[] arr) {
        int n = arr.length;
        
        // Compute LIS and LDS arrays
        int[] lis = computeLIS(arr);
        int[] lds = computeLDS(arr);

        // Calculate the length of the Longest Bitonic Subsequence
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            // Bitonic subsequence length at i is lis[i] + lds[i] - 1
            maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
        }

        return maxLength;
    }

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