Maximize consecutive elements in an array after modification

Array Dynamic Programming Sorting

33.6% acceptance

Feb 25, 2026

178

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. Return the maximum number of elements that you can select.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_selected_elements(mut nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    nums.sort();
    let mut dp: HashMap<i32, i32> = HashMap::new();
    for &x in &nums {
      let v1 = dp.get(&(x-1)).copied().unwrap_or(0) + 1;
      let v2 = dp.get(&x).copied().unwrap_or(0) + 1;
      *dp.entry(x).or_insert(0) = dp.get(&x).copied().unwrap_or(0).max(v1);
      *dp.entry(x+1).or_insert(0) = dp.get(&(x+1)).copied().unwrap_or(0).max(v2);
    }
    *dp.values().max().unwrap()
  }
}