FastPrep

Description

Solutions

Longest Concave Subsequence

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

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]. Return 3, 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.

Constraints:

1 ≤ n ≤ 10^5
1 ≤ arr[i] ≤ n
arr is a permutation of integers from 1 to n.