FastPrepFind Maximum Beauty

Find Maximum Beauty

The D.E. Shaw Group logoThe D.E. Shaw Group● MediumOA
Learn

Problem statement

Given an array arr, you can perform the following operation:

  • Remove an element from any position in the array. The order of other elements should be maintained after removing the element.

You're allowed to perform this operation until the arr size becomes 1.

Now the beauty of an array is equal to the number of elements where a[i] = i (the array is 1 indexed).

Given an array, find the maximum beauty after performing the above operation.

Function

findMaximumBeauty(arr: int[]) → int

Complete the function findMaximumBeauty in the editor.

findMaximumBeauty has the following parameter:

  1. int[] arr: an array of integers

Returns int: the maximum beauty of the array

Examples

Example 1

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

Following the operations described in the problem statement:

  1. Remove the first 3, then arr becomes [1, 2, 5, 4, 5, 3].
  2. Remove 3, then arr becomes [1, 2, 5, 4, 5].

The beauty of the final array is 4. (where a[i] = i).

Constraints

  • unknown for now

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights
public int findMaximumBeauty(int[] arr) {
    // write your code here
}
arr[1, 3, 2, 5, 4, 5, 3]
expected4
Checking account…