DSA

Maximum Length of Bitonic Subsequence

DP approach.

August 8, 2026
PatternLongest Increasing Subsequence
Solve on GeeksforGeeks
Key insighttry it first, then reveal

A bitonic subsequence rises then falls, so every element can serve as the "peak" that separates the increasing and decreasing halves.

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.

cpp
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;
    }
    
};