Maximize Points by Deleting Values and Their Neighbors

Quick Overview

Maximize the score from removing integer occurrences when each choice also removes neighboring values, with duplicates and a sparse value range.

Maximize Points by Deleting Values and Their Neighbors

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given an array of positive integers `nums`. You may repeatedly choose an occurrence of a value `v` that is still present, remove that occurrence, and earn `v` points. That operation also removes every remaining occurrence of `v - 1` and `v + 1`, earning no points for those additional removals. Return the maximum total points you can earn. Other occurrences of `v` remain available unless you choose to remove them in later operations. ### Input - `nums`: an array of positive integers. Duplicate values are allowed. ### Output Return the maximum achievable total score as an integer. ### Constraints and Edge Cases - For this practice version, `1 <= nums.length <= 20000` and `1 <= nums[i] <= 1000000000`. - Input order does not affect which values an operation removes. - Removing an occurrence never earns points for any neighboring values removed as a side effect. - Values need not fill a continuous range, and the largest value can be much larger than the number of elements. - The result may exceed the range of a signed 32-bit integer. Use a numeric representation that holds the total exactly. ### Example 1 ```text nums = [2, 2, 3, 3, 3, 4] output = 9 ``` Choosing the three occurrences of `3` earns `9` points. Choosing both `2` occurrences and the `4` instead earns only `8`. ### Example 2 ```text nums = [1, 1, 3, 1000000000] output = 1000000005 ``` All occurrences can contribute to the score because none of their values differ by one.

Overview: Maximize the score from removing integer occurrences when each choice also removes neighboring values, with duplicates and a sparse value range.

|Home/Coding & Algorithms/Microsoft
Microsoft logo
Microsoft
Aug 25, 2026
mediumSoftware EngineerOnline AssessmentCoding & Algorithms
0
0

You are given an array of positive integers nums. You may repeatedly choose an occurrence of a value v that is still present, remove that occurrence, and earn v points. That operation also removes every remaining occurrence of v - 1 and v + 1, earning no points for those additional removals.

Return the maximum total points you can earn. Other occurrences of v remain available unless you choose to remove them in later operations.

Input

  • nums : an array of positive integers. Duplicate values are allowed.

Output

Return the maximum achievable total score as an integer.

Constraints and Edge Cases

  • For this practice version, 1 <= nums.length <= 20000 and 1 <= nums[i] <= 1000000000 .
  • Input order does not affect which values an operation removes.
  • Removing an occurrence never earns points for any neighboring values removed as a side effect.
  • Values need not fill a continuous range, and the largest value can be much larger than the number of elements.
  • The result may exceed the range of a signed 32-bit integer. Use a numeric representation that holds the total exactly.

Example 1

nums = [2, 2, 3, 3, 3, 4]
output = 9

Choosing the three occurrences of 3 earns 9 points. Choosing both 2 occurrences and the 4 instead earns only 8.

Example 2

nums = [1, 1, 3, 1000000000]
output = 1000000005

All occurrences can contribute to the score because none of their values differ by one.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...