Q11 Longest Bitonic subsequence | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T-->0)
        {
            int n = Integer.parseInt(br.readLine().trim());
            String s = br.readLine().trim();
            String[] s1 = s.split(" ");
            int[] nums = new int[n];
            for(int i = 0; i < s1.length; i++)
                nums[i] = Integer.parseInt(s1[i]);
            Solution ob = new Solution();
            int ans = ob.LongestBitonicSequence(nums);
            System.out.println(ans);           
        }
    }
}

// } Driver Code Ends


//User function Template for Java

class Solution
{
    public int[] LIS(int[] nums ){
        int n = nums.length;
        
        int dp[] = new int[n];
        dp[0] = 1;  // for 1 length LIS will be 1 length
        
        for(int i = 1 ; i < n ; i++){
            
            for(int j = i-1 ; j>= 0 ; j--){
                
                //finding max in previous smaller elements
                if(nums[j] < nums[i])
                dp[i] = Math.max(dp[i] , dp[j]);
            }
            
            //adding +1 for current element
            dp[i] +=1;
            
        }
        
        return dp;
    }
    
    public int[] LDS(int[] nums){
        int n = nums.length;
        
        int dp[] = new int[n];
        dp[n-1] = 1;  // for 1 length LDS will be 1 length
        
        for(int i = n-2 ; i >=0 ; i--){
            
            for(int j = i+1 ; j< n ; j++){
                
                //finding max in previous smaller elements
                if(nums[j] < nums[i])
                dp[i] = Math.max(dp[i] , dp[j]);
            }
            
            //adding +1 for current element
            dp[i] +=1;
            
        }
        
        return dp;
    }
    public int LongestBitonicSequence(int[] nums)
    {
        /* for LBS we will need LIS and LDS , storage - 2 1D arrays for LIS and LDS
        meaning - 
        every cell will store LIS ending at that element this is going from left to right
        
        every cell will store LDS ending at that element this is going from right to left       
        
        LDS can be understood as LIS but in reverse array
        */ 
        
        int LIS[] = LIS(nums);
        
        //for LDS we can find reverse LIS 
        int LDS[] = LDS(nums);
        
        
        //now find max biotonic sequence for every element by LIS+LDS -1 and return max
        //-1 for the repeated element which exists in both LIS and LDS
        
        int ans = 0;
        for(int i = 0 ; i < nums.length ;i++){
            
            int biotonic = LIS[i] + LDS[i] -1;
            
            ans = Math.max(ans , biotonic);
        }
        
        return ans;
        
    }
}