Choose a Highest-Sum Distinct Subarray

Quick Overview

Choose a Highest-Sum Distinct Subarray. Erase exactly one nonempty contiguous subarray of the positive array nums. Its values must all be distinct, and its score is their sum. Return the largest score available.

Choose a Highest-Sum Distinct Subarray

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

### Problem Erase exactly one nonempty contiguous subarray of the positive array `nums`. Its values must all be distinct, and its score is their sum. Return the largest score available. ```cpp class Solution { public: int maximumUniqueSubarray(vector<int>& nums); }; ``` ### Examples **Example 1:** ```text nums = [2,7,2,4] Output: 13 Explanation: The final three values [7,2,4] are distinct and total 13. ``` **Example 2:** ```text nums = [6,6,6] Output: 6 Explanation: A distinct-valued subarray can contain only one of the entries. ``` ### Constraints - `1 <= nums.length <= 10^5`. - `1 <= nums[i] <= 10^4`. ### Clarifying Questions The chosen entries must be contiguous, not an arbitrary selection of distinct values. Positivity is part of the source domain. ```hint Inspect the structure What makes a candidate block eligible, and can it be empty or noncontiguous? ``` ### Reasoning checkpoints - Require a nonempty contiguous block with no repeated value. - Prove the largest achievable score in the stated positive-value domain. ### Optional extensions What additional technique would be needed if negative values were permitted?

Overview: Choose a Highest-Sum Distinct Subarray. Erase exactly one nonempty contiguous subarray of the positive array nums. Its values must all be distinct, and its score is their sum. Return the largest score available.

Google logo
Google
Source window: 0–6 months · as of Oct 21, 2026
mediumSoftware EngineerOtherCoding & Algorithms
0
0

Problem

Erase exactly one nonempty contiguous subarray of the positive array nums. Its values must all be distinct, and its score is their sum. Return the largest score available.

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums);
};

Examples

Example 1:

nums = [2,7,2,4]
Output: 13
Explanation: The final three values [7,2,4] are distinct and total 13.

Example 2:

nums = [6,6,6]
Output: 6
Explanation: A distinct-valued subarray can contain only one of the entries.

Constraints

  • 1 <= nums.length <= 10^5 .
  • 1 <= nums[i] <= 10^4 .

Clarifying Questions Guidance

The chosen entries must be contiguous, not an arbitrary selection of distinct values. Positivity is part of the source domain.

Reasoning checkpoints

  • Require a nonempty contiguous block with no repeated value.
  • Prove the largest achievable score in the stated positive-value domain.

Optional extensions

What additional technique would be needed if negative values were permitted?