Problem Brief

Longest Concave Subsequence

NEW GRADOA

See Tiktok online assessment and hiring insights

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

1Example 1

Input

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

Output

Explanation

There are three longest subsequences: [4, 2, 6], [4, 2, 5], and [4, 2, 3]. Return 3, the length of these subsequences.

2Example 2

Input

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

Output

Explanation

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

3Example 3

Input

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

Output

Explanation

My subsequence of 2 elements satisfies the requirements.

Constraints

Limits and guarantees your solution can rely on.

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