Maximum Beauty of an Array After Applying Operation
You are given a 0-indexed array nums and a non-negative integer k.
In one operation, you can do the following:
- Choose an index
ithat hasn't been chosen before from the range[0, nums.length - 1]. - Replace
nums[i]with any integer from the range[nums[i] - k, nums[i] + k].
The beauty of the array is the length of the longest subsequence consisting of equal elements.
Return the maximum possible beauty of the array nums after applying the operation any number of times.
Note that you can apply the operation to each index only once.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the order of the remaining elements.
Example 1
Input
nums = [4,6,1,2], k = 2Output
3By changing 6 and 2 to 4, the array can contain a subsequence of three equal elements, and 3 is the maximum possible length.
Example 2
Input
nums = [1,1,1,1], k = 10Output
4No operations are needed because the whole array already consists of four equal elements.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i], k <= 10^5