#2779
Maximum Beauty of an Array After Applying Operation
specialist · 740 · lc medium +31 · verified · 58.3% accepted · 1,271 likes · top 54%
Description
A 0-indexed array nums and a non-negative integer k are given. For each index i (chosen at most once), you may replace nums[i] with any integer from [nums[i] - k, nums[i] + k].
The beauty of the array is the length of the longest subsequence of equal elements.
Return the maximum beauty achievable after applying the operation any number of times.
Note that each index may be operated on at most once.
A subsequence is an array generated from the original by deleting some elements (possibly none) while preserving relative order.
Example 1:
Input: nums = [4,6,1,2], k = 2
Output: 3
Explanation: In this example, we apply the following operations:
- Choose index 1, replace it with 4 (from range [4,8]), nums = [4,4,1,2].
- Choose index 3, replace it with 4 (from range [0,4]), nums = [4,4,1,4].
After the applied operations, the beauty of the array nums is 3 (subsequence consisting of indices 0, 1, and 3).
It can be proven that 3 is the maximum possible length we can achieve.
Example 2:
Input: nums = [1,1,1,1], k = 10
Output: 4
Explanation: In this example we don't have to apply any operations.
The beauty of the array nums is 4 (whole array).
Code
1
2
3