Q$4.$ Longest Concave Subsequence

A concave subsequence is a subsequence where the first and last elements are greater than all other elements in between. For example, $[100,0,25,11,200]$ is concave, while $[100,0,110,200]$ is not since the third element is greater than the first element.

Given an array that contains a permutation of n integers, arr$[$n$],$ determine length of the longest concave subsequence.

A permutation is a sequence of integers from $1$ to n that contains each number exactly once. For example $[1,3,2]$ is a permutation while $[1,2,1]$ and $[1,2,4]$ are not.

A subsequence is derived from a sequence by deleting zero or more elements without changing the order of the remaining elements. For example $[3,4]$ is a subsequence of $[5,3,2,4],$ but $[4,3]$ is not.

Example

n $=6$

arr $=[4,2,6,5,3,1]$

There are three longest subsequences: $[4,2,6],[4,2,5],$ and $[4,2,3].$

Return $3,$ the length of these subsequences.

Function Description

Complete the function maxLength in the editor below.

maxLength has the following parameter:

int arr$[$n$]$: the array

returns

int: the length of the longest subsequence having the required property

constraints

$1<=$ n $<=10^5$

$1<=$ arr$[$i$]<=$ n

arr is a permutation of integers from $1$ to n$.$

Sample Input $0$

$5$ arr$[]$ size n $=5$

$3$ arr$[]=[3,1,5,2,4]$

$1$

$5$

$2$

$4$

Sample Output $0$

$4$

Explanation

The longest subsequence satisfying the requirement is $[3,1,2,4].$

Sample Input $1$

$5$ arr$[]$ size n $=5$

$1$ arr $=[1,2,3,4,5]$

$2$

$3$

$4$

$5$

Sample Output $1$

$2$

Explanation

my subsequence of $2$ elements satisfies the requirements.