3041. Maximize Consecutive Elements in an Array After Modification
Difficulty: Hard
Topics: Senior Staff, Array, Dynamic Programming, Sorting, Biweekly Contest 124
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.
Example 3:
- Input: nums = [1,2,3]
- Output: 3
Example 4:
- Input: nums = [1,1,1,1]
- Output: 2
Example 5:
- Input: nums = [2,2,2,2]
- Output: 2
Example 6:
- Input: nums = [3,4,5,6]
- Output: 4
Example 7:
- Input: nums = [1,3,5,7]
- Output: 2
Example 8:
- Input: nums = [1,2,2,3,3,4]
- Output: 5
Example 9:
- Input: nums = [5]
- Output: 1
Example 10:
- Input: nums = [1,1,2,2,3,3]
- Output: 4
Constraints:
1 <= nums.length <= 10⁵1 <= nums[i] <= 10⁶
Hint:
- Sort the array and try using dynamic programming.
- Let
dp[i]be the length of the longest consecutive elements ending at element at indexiin the sorted array.
Solution:
We sort the array and use a hash-map-based dynamic programming approach where dp[v] stores the maximum length of a consecutive sequence ending at value v. For each element, we try two choices: keep it as-is, or increase it by 1, and update the DP state accordingly while ensuring the same element is never reused in the same sequence.
Approach
- Sort
numsso that we process values in increasing order, guaranteeing that any consecutive sequence we build is contiguous in value space. - Maintain a map
dpwheredp[v]= maximum length of a consecutive selected sequence whose last (largest) value isv. - For each element
xin sorted order, consider two options (each element can be increased by at most 1):- Keep as
x: extend the best sequence ending atx-1, giving lengthdp[x-1] + 1. Updatedp[x]. - Increase to
x+1: extend the best sequence ending atx(captured before the current element is applied), giving lengtholdX + 1. Updatedp[x+1].
- Keep as
- Snapshot
oldX = dp[x]andoldPrev = dp[x-1]before any writes, so the two options cannot double-use the current element. - Track the global maximum across all updates.
Let's implement this solution in PHP: 3041. Maximize Consecutive Elements in an Array After Modification
<?php /** * @param Integer[] $nums * @return Integer */ function maxSelectedElements(array $nums): int { ... ... ... /** * go to ./solution.php */ } // Test cases echo maxSelectedElements([2,1,5,1,1]) . "\n"; // Output: 3 echo maxSelectedElements([1,4,7,10]) . "\n"; // Output: 1 echo maxSelectedElements([1,2,3]) . "\n"; // Output: 3 echo maxSelectedElements([1,1,1,1]) . "\n"; // Output: 2 echo maxSelectedElements([2,2,2,2]) . "\n"; // Output: 2 echo maxSelectedElements([3,4,5,6]) . "\n"; // Output: 4 echo maxSelectedElements([1,3,5,7]) . "\n"; // Output: 2 echo maxSelectedElements([1,2,2,3,3,4]) . "\n"; // Output: 5 echo maxSelectedElements([5]) . "\n"; // Output: 1 echo maxSelectedElements([1,1,2,2,3,3]) . "\n"; // Output: 4 ?> Explanation
- Why
oldXmatters: When increasingxtox+1, we want to append to a sequence that ended at valuexbefore the current element was used. If we readdp[x]after the "keep asx" update, we would be extending a sequence that already includes the current element — violating "each element used once." Hence we snapshotoldXfirst. - Why
dp[x-1]is safe to read directly:dp[x-1]is only modified when processing elements of valuex-2(which increase tox-1) orx-1itself. Since the array is sorted, an element of valuex-1has already been processed anddp[x-1]now reflects the best achievable state — exactly what we need. - Why we take
maxwhen writing:-
dp[x]may already hold a sequence built by a previous elementx-1increased tox. We keep whichever is longer. -
dp[x+1]may already hold a sequence built by a previous elementxincreased tox+1. We keep whichever is longer.
-
- Why sorting is essential: It ensures that when we consider extending a sequence ending at
x-1orx, all candidate predecessors have already been processed and their DP values are final. - Why the answer is
max(dp[x], dp[x+1])after each element: These are the only two entries touched for the currentx, so the running maximum correctly captures the longest sequence across all values.
Complexity Analysis
- Time Complexity:
O(n log n)— dominated by sortingnums. The DP pass isO(n)with hash map operations averagingO(1). - Space Complexity:
O(n)— thedpmap holds at mostO(n)distinct keys (values and value+1 for each element).
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:
