Skip to content

Maximize Consecutive Elements in an Array After Modification⚓︎

Link

Solution⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSelectedElements(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> f;
        for (int x : nums) {
            f[x + 1] = f[x] + 1;
            f[x] = f[x - 1] + 1;
        }

        int ans = 0;
        for (auto& [_, res] : f) {
            ans = max(ans, res);
        }
        return ans;
    }
};

Another way of writing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxSelectedElements(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        vector<int> f(1e6 + 10);
        f[nums[0]] = 1;
        f[nums[0] + 1] = 1;
        for (int i = 1; i < n; i++) {
            f[nums[i] + 1] = f[nums[i]] + 1;
            f[nums[i]] = f[nums[i] - 1] + 1;
        }

        int ans = 0;
        for (int i = 0; i < 1e6 + 5; i++) {
            ans = max(ans, f[i]);
        }
        return ans;
    }
};