35.Longest Bitonic Sequence

 int longestBitonicSubsequence(vector<int>& arr, int n)

{

    // Write your code here.

    int i,j;

    int dp1[n+1],dp2[n+2];

    for(i=0;i<=n;i++)

    {

        dp1[i]=1;

        dp2[i]=1;

    }

    for(i=1;i<n;i++)

    {

         for(j=0;j<i;j++)

         {

             if(arr[j]<arr[i])

             {

                 dp1[i]=max(dp1[i],1+dp1[j]);

             }

         }

    }

        for(i=n-1;i>=0;i--)

    {

         for(j=n-1;j>i;j--)

         {

             if(arr[j]<arr[i])

             {

                 dp2[i]=max(dp2[i],1+dp2[j]);

             }

         }

    }

    int ans=0;

    for(i=0;i<n;i++)

    {

        int r=dp1[i]+dp2[i]-1;

        ans=max(ans,r);

    }

    return ans;

}