Skip to Content
LeetCode The Hard Way
3000 - 3099

3041 - Maximize Consecutive Elements in an Array After Modification (Hard)

https://leetcode.com/problems/maximize-consecutive-elements-in-an-array-after-modification

Problem Statement

You are given a 0-indexed array nums consisting of positive integers.

Initially, you can increase the value of any element in the array by at most 1.

After that, you need to select one or more elements from the final array such that those elements are consecutive when sorted in increasing order. For example, the elements [3, 4, 5] are consecutive while [3, 4, 6] and [1, 1, 2, 3] are not.

Return the maximum number of elements that you can select.

Example 1:

Input: nums = [2,1,5,1,1]
Output: 3
Explanation: We can increase the elements at indices 0 and 3. The resulting array is nums = [3,1,5,2,1].
We select the elements [3,1,5,2,1] and we sort them to obtain [1,2,3], which are consecutive.
It can be shown that we cannot select more than 3 consecutive elements.

Example 2:

Input: nums = [1,4,7,10]
Output: 1
Explanation: The maximum consecutive elements that we can select is 1.

Constraints:

  • 1 <= nums.length <= 1e5
  • 1 <= nums[i] <= 1e6

Approach 1: Dynamic Programming

Each element can either stay the same or increase by 11. We want to choose as many elements as possible so that, after sorting the chosen elements, every number is exactly one greater than the previous number. Duplicate values cannot appear in the chosen sequence.

First, we sort numsnums. This lets us process smaller numbers before larger numbers and build consecutive sequences by adding elements to their ends.

We use dpdp to store the longest consecutive sequence ending at each value. For example, if dp[4]=3dp[4] = 3, we can form a sequence of length 33 ending at 44, namely [2,3,4][2, 3, 4]. A defaultdict(int)defaultdict(int) returns 00 for missing keys, meaning that no sequence ending at that value has been found yet.

For each number xx, we first consider increasing it to x+1x + 1. It can extend a sequence ending at xx, so we set dp[x+1]=dp[x]+1dp[x + 1] = dp[x] + 1. Then we consider leaving it unchanged. It can extend a sequence ending at x−1x - 1, so we set dp[x]=dp[x−1]+1dp[x] = dp[x - 1] + 1.

The order of these updates is important. We update dp[x+1]dp[x + 1] before dp[x]dp[x] so that the increased option uses a sequence built only from earlier elements. Otherwise, we might accidentally use the current element twice.

The time complexity is O(nlog⁡n)O(n \log n) and the space complexity is O(n)O(n).

Written by@wkw
class Solution:
    def maxSelectedElements(self, nums: List[int]) -> int:
        dp = defaultdict(int)
        res = 0
        for x in sorted(nums):
            dp[x + 1] = dp[x] + 1
            dp[x] = dp[x - 1] + 1
            res = max(res, dp[x], dp[x + 1])
        return res

On this page