1. Description
Given an array nums of positive integers, you may increase each element by at most 1.
After these modifications, select one or more elements that form a consecutive sequence when sorted. Selected values must be distinct and differ by exactly 1 between neighbors.
Return the largest possible number of selected elements.
2. Example
Example 1
Input: nums = [2,1,5,1,1]
Output: 3
Explanation: Increase nums[0] and nums[3] by 1 to obtain [3,1,5,2,1]. Selecting 3, 1, and 2 gives the consecutive sequence [1,2,3] after sorting. No selection of more than three elements is possible.
Example 2
Input: nums = [1,4,7,10]
Output: 1
Explanation: Even after increasing elements by 1, no two values can become consecutive, so the largest selection has one element.
3. Constraints
- 1 <= nums.length <= 10$^5$
- 1 <= nums[i] <= 10$^6$
4. Solutions
Sorting && Dynamic Programming
n = nums.size()
Time complexity: O(n log n)
Space complexity: O(log n)
| |