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 the 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.
Function Description
Complete the function maxLength in the editor.
maxLength has the following parameter:
int arr[n]: the array
Returns
int: the length of the longest subsequence having the required property
Example 1:
Input: arr = [4, 2, 6, 5, 3, 1]
Output: 3
Explanation:There are three longest subsequences:[4, 2, 6],[4, 2, 5], and[4, 2, 3]. Return3, the length of these subsequences.
Example 2:
Input: arr = [3, 1, 5, 2, 4]
Output: 4
Explanation:The longest subsequence satisfying the requirement is [3, 1, 2, 4].
Example 3:
Input: arr = [1, 2, 3, 4, 5]
Output: 2
Explanation:My subsequence of 2 elements satisfies the requirements.
1 ≤ n ≤ 10^51 ≤ arr[i] ≤ narris a permutation of integers from1ton.
input:
output: