3041. Maximize Consecutive Elements in an Array After Modification

LeetCode 力扣

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxSelectedElements(vector<int> &nums) {
        sort(nums.begin(), nums.end());

        int prev = nums.front();
        int a = 1, b = 1;
        int max_length = 1;
        for (int i = 1, n = nums.size(); i < n; ++i) {
            int num = nums[i];

            if (num == prev) {
                b = max(a + 1, b);
            } else if (num == prev + 1) {
                int temp = max(b, a + 1);
                b = b + 1;
                a = temp;
            } else if (num == prev + 2) {
                a = b + 1;
                b = 1;
            } else {
                a = b = 1;
            }

            max_length = max({max_length, a, b});
            prev = num;
        }

        return max_length;
    }
};
comments powered by Disqus