Maximize Beauty 🐱
MathWorks● MediumFULLTIMEOAProblem statement
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 deletearr[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
maximizeBeauty(arr: int[]) → int
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
Examples
Example 1
arr = [1, 3, 2, 5, 4, 5, 3]return = 4One optimal sequence of operations is shown.
- Choose
i = 2, deletearr[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
arr = [6, 3, 2, 4, 3, 4]return = 3One optimal sequence of operations is shown.
- Choose
i = 2, deletearr[2] = 3;arr = [6, 2, 4, 3, 4]. - Choose
i = 3, deletearr[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
arr = [1, 3, 2, 5, 4, 5, 3]return = 4One 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]≤ 105