FastPrep
Problem · Array

Find Maximum Beauty

Learn this problem
● MediumThe D. E. Shaw GroupOA

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

drafts saved locally
public int findMaximumBeauty(int[] arr) {
    // write your code here
}
arr[1, 3, 2, 5, 4, 5, 3]
expected4
checking account