FastPrep

Description

Solutions

Submission

Maximize Beauty 🐱

🔥 FULLTIME

The beauty of an array of length m is defined as the number of integers i (1 ≤ i ≤ m) such that a[i] = i.

Given an array arr of n integers, the following operation can be performed on the array while its length is greater than 1:

Choose some i (1 ≤ i ≤ length of the array) and delete arr[i] without changing the order of the remaining elements.

Find the maximum possible beauty of the array after performing this operation any number of times.

Function Description

Complete the function maximizeBeauty in the editor below.

maximizeBeauty has the following parameter:

int arr[n]: the given array

Returns

int: the maximum possible beauty of the array

Example 1:

Input:  arr = [1, 3, 2, 5, 4, 5, 3]
Output: 4 
Explanation:
One optimal sequence of operations is shown.
    
Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5].

Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5]

The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5.
Return 4.
    
Note that there can be more than one final array with maximum beauty, like [1, 2, 5, 4, 5, 3] in this case.

Example 2:

Input:  arr = [6, 3, 2, 4, 3, 4]
Output: 3 
Explanation:
One optimal sequence of operations is shown.
   
Choose i = 2, delete arr[2] = 3; arr = [6, 2, 4, 3, 4].

Choose i = 3, delete arr[3] = 4; arr = [6, 2, 3, 4].
      
arr[2] = 2, arr[3] = 3, and arr[4] = 4.

The maximum possible beauty of the array is 3.

Note that there can be more than one final arr with max beauty, like [1, 2, 5, 4, 5, 3] in this case.

Example 3:

Input:  arr = [1, 3, 2, 5, 4, 5, 3]
Output: 4 
Explanation:
One optimal sequence of operations is shown.

Choose i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5, 3]

Choose i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5]

The beauty of arr is 4 since arr[1] = 1, arr[2] = 2, arr[4] = 4, and arr[5] = 5.

Return 4.

Constraints:

1 ≤ n ≤ 2000

1 ≤ arr[i] ≤ 10⁵