Maximum Length of Bitonic Subsequence

Practice Link

Given an array of positive integers. Find the maximum length of Bitonic subsequence. A subsequence of array is called Bitonic if it is first strictly increasing, then strictly decreasing. Return the maximum length of bitonic subsequence.

Note : A strictly increasing or a strictly decreasing sequence should not be considered as a bitonic sequence

DP APPROACH#

A bitonic subsequence rises then falls, so every element can serve as the "peak" that separates the increasing and decreasing halves. We compute two auxiliary arrays:

• lis[i] — length of the Longest Increasing Subsequence ending at index i (left half up to the peak).
• lds[i] — length of the Longest Decreasing Subsequence starting at index i (right half from the peak).

For each candidate peak i, the bitonic length is lis[i] + lds[i] - 1 (subtracting 1 because the peak itself is counted in both arrays). We require both lis[i] > 1 and lds[i] > 1 to ensure the sequence is strictly increasing on the left and strictly decreasing on the right — a purely increasing or purely decreasing sequence doesn't qualify. Both auxiliary arrays are built with the standard O(n^2) LIS DP, so the overall complexity is O(n^2) time and O(n) space.

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. Therefore the length of the longest bitonic subsequence at pivot [i] will be dp1[i] + dp2[i] - 1.

class Solution {
  public:
  int liscall(int n, vector<int> nums, vector<int> &lis)
	{
        lis[0] = 1;
        for(int i=1;i<n;i++)
        {
            lis[i]= 1;
            for(int j=0;j<i;j++)
            {
                if(nums[i] > nums[j])
                {
                    lis[i] = max(lis[i], lis[j] + 1);
                }
            }
        }

	}
	int ldscall(int n, vector<int> nums, vector<int> &lds)
	{
        lds[n-1] = 1;
        for(int i=n-2;i>=0;i--)
        {
            lds[i]= 1;
            for(int j=n-1;j>i;j--)
            {
                if(nums[i] > nums[j])
                {
                    lds[i] = max(lds[i], lds[j] + 1);
                }
            }
        }

	}
    int LongestBitonicSequence(int n, vector<int> &arr) {
        
        
        vector<int> lis(arr.size());
	    vector<int> lds(arr.size());
	    
	    liscall(n,arr,lis);
	    ldscall(n,arr, lds);
	    
	    int maxLength = 0;
	    for(int i=0;i<arr.size();i++)
	    {
            // Check if both LIS and LDS are valid 
            // for the current index
	        if(lis[i]> 1 && lds[i]>1)
	            maxLength = max(maxLength, lis[i] + lds[i] - 1);
	    }
	    return maxLength < 3 ? 0: maxLength;
    }
    
};