How should I practice Longest Concave Subsequence?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tiktok online assessment problems in FastPrep.

Is Longest Concave Subsequence associated with Tiktok?

FastPrep tags this as a Tiktok coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Longest Concave Subsequence

Learn this problem

● HardTiktokNEW GRADOA

See Tiktok hiring insights

Problem statement

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

maxLength(arr: int[]) → int

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

Examples

Example 1

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

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

Example 2

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

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

Example 3

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

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.