Problem · Dynamic Programming
Maximize Beauty 🐱
Learn this problemProblem 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
Choose
The beauty of
i = 2, delete arr[2] = 3; arr = [1, 2, 5, 4, 5].i = 6, delete arr[6] = 3; arr = [1, 2, 5, 4, 5]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
Choose
i = 2, delete arr[2] = 3; arr = [6, 2, 4, 3, 4].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
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
n ≤ 2000arr[i] ≤ 105