Maximum Erasure Value

Problem

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Examples

Example 1:

Input:
nums = [4,2,4,5,6]
Output:
 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input:
nums = [5,2,1,2,5,2,1,2,5]
Output:
 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Solution

Method 1 – Sliding Window with HashSet

This problem is similar to [Longest Substring Without Repeating Characters](longest-substring-without-repeating-characters).

Intuition

To find the maximum sum of a subarray with all unique elements, we use a sliding window to maintain a range of non-repeating numbers. By expanding the window to the right and shrinking it from the left when duplicates are found, we can efficiently track the sum of unique elements and update the answer.

Approach

1. Initialize a set to keep track of unique elements in the current window.
2. Use two pointers (left and right) to define the window boundaries.
3. Move the right pointer forward, adding elements to the set and sum if they are not present.
4. If a duplicate is found, move the left pointer forward, removing elements from the set and subtracting from the sum until the duplicate is removed.
5. Update the maximum sum after each addition.
6. Continue until the right pointer reaches the end of the array.

Code

C++

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> set;
        int ans = 0, sum = 0, left = 0;
        for (int right = 0; right < nums.size(); ++right) {
            while (set.count(nums[right])) {
                set.erase(nums[left]);
                sum -= nums[left++];
            }
            set.insert(nums[right]);
            sum += nums[right];
            ans = max(ans, sum);
        }
        return ans;
    }
};

Go

func maximumUniqueSubarray(nums []int) int {
    set := make(map[int]bool)
    ans, sum, left := 0, 0, 0
    for right := 0; right < len(nums); right++ {
        for set[nums[right]] {
            set[nums[left]] = false
            sum -= nums[left]
            left++
        }
        set[nums[right]] = true
        sum += nums[right]
        if sum > ans {
            ans = sum
        }
    }
    return ans
}

Java

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0, sum = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            while (set.contains(nums[right])) {
                set.remove(nums[left]);
                sum -= nums[left++];
            }
            set.add(nums[right]);
            sum += nums[right];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun maximumUniqueSubarray(nums: IntArray): Int {
        val set = mutableSetOf<Int>()
        var ans = 0
        var sum = 0
        var left = 0
        for (right in nums.indices) {
            while (nums[right] in set) {
                set.remove(nums[left])
                sum -= nums[left]
                left++
            }
            set.add(nums[right])
            sum += nums[right]
            ans = maxOf(ans, sum)
        }
        return ans
    }
}

Python

type Solution:
    def maximumUniqueSubarray(self, nums: list[int]) -> int:
        set_: set[int] = set()
        ans: int = 0
        sum_: int = 0
        left: int = 0
        for right in range(len(nums)):
            while nums[right] in set_:
                set_.remove(nums[left])
                sum_ -= nums[left]
                left += 1
            set_.add(nums[right])
            sum_ += nums[right]
            ans = max(ans, sum_)
        return ans

Rust

impl Solution {
    pub fn maximum_unique_subarray(nums: Vec<i32>) -> i32 {
        use std::collections::HashSet;
        let mut set = HashSet::new();
        let (mut ans, mut sum, mut left) = (0, 0, 0);
        for right in 0..nums.len() {
            while set.contains(&nums[right]) {
                set.remove(&nums[left]);
                sum -= nums[left];
                left += 1;
            }
            set.insert(nums[right]);
            sum += nums[right];
            ans = ans.max(sum);
        }
        ans
    }
}

TypeScript

class Solution {
    maximumUniqueSubarray(nums: number[]): number {
        const set = new Set<number>();
        let ans = 0, sum = 0, left = 0;
        for (let right = 0; right < nums.length; right++) {
            while (set.has(nums[right])) {
                set.delete(nums[left]);
                sum -= nums[left++];
            }
            set.add(nums[right]);
            sum += nums[right];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), since each element is added and removed from the set at most once.
• 🧺 Space complexity: O(n), for storing up to n unique elements in the set.