FastPrepMaximize Array Beauty After Deletions

Maximize Array Beauty After Deletions

Point72 logoPoint72● HardFULLTIMEOA
Learn

Problem statement

You are given an integer array values. Delete any number of elements while preserving the relative order of the elements that remain. At least one element must remain.

The beauty of the final array is the number of its 1-indexed positions i for which the value at that position equals i.

Return the maximum beauty obtainable after deletions.

Function

maximizeArrayBeauty(values: int[]) → int

Examples

Example 1

values = [2,2,1,3,4]return = 3

Delete the third element to obtain [2,2,3,4]. Its values match positions 2, 3, and 4.

Example 2

values = [4,1,2,3,4]return = 4

Delete the first element. The remaining array is [1,2,3,4], so every position contributes to the beauty.

Example 3

values = [2,3,4,5]return = 0

No non-empty subsequence can place any of these values at an equal 1-indexed position.

Constraints

  • 1 <= values.length <= 200000
  • -10^9 <= values[i] <= 10^9

More Point72 problems

See Point72 hiring insights
public int maximizeArrayBeauty(int[] values) {
  // write your code here
}
values[2,2,1,3,4]
expected3
Checking account…