Problem

You are given an integer array nums.

You are allowed to delete any number of elements from nums without making it empty. After performing the deletions, select a subarray of nums such that:

  1. All elements in the subarray are unique.
  2. The sum of the elements in the subarray is maximized.

Return the maximum sum of such a subarray.

Example 1

1
2
3
4
5

Input: nums = [1,2,3,4,5]
Output: 15
Explanation:
Select the entire array without deleting any element to obtain the maximum
sum.

Example 2

1
2
3
4
5

Input: nums = [1,1,0,1,1]
Output: 1
Explanation:
Delete the element `nums[0] == 1`, `nums[1] == 1`, `nums[2] == 0`, and
`nums[3] == 1`. Select the entire array `[1]` to obtain the maximum sum.

Example 3

1
2
3
4
5

Input: nums = [1,2,-1,-2,1,0,-1]
Output: 3
Explanation:
Delete the elements `nums[2] == -1` and `nums[3] == -2`, and select the
subarray `[2, 1]` from `[1, 2, 1, 0, -1]` to obtain the maximum sum.

Constraints

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

Examples

Solution

Method 1 – Sliding Window with Hash Set

Intuition

To maximize the sum of a subarray with unique elements, we use a sliding window and a hash set to track the current window’s elements. If a duplicate is found, we shrink the window from the left until all elements are unique, always updating the maximum sum.

Approach

  1. Initialize a hash set to store unique elements in the current window.
  2. Use two pointers (l and r) to define the window.
  3. Expand the window by moving r and adding nums[r] to the set and sum.
  4. If a duplicate is found, move l forward, removing elements from the set and sum until the window is unique.
  5. Track and update the maximum sum found.
  6. Return the maximum sum.

Complexity

  • ⏰ Time complexity: O(n) — Each element is added and removed from the set at most once.
  • 🧺 Space complexity: O(n) — For the hash set.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maximumUniqueSubarraySum(vector<int>& nums) {
        unordered_set<int> s;
        int l = 0, ans = 0, sum = 0;
        for (int r = 0; r < nums.size(); ++r) {
            while (s.count(nums[r])) {
                s.erase(nums[l]);
                sum -= nums[l++];
            }
            s.insert(nums[r]);
            sum += nums[r];
            ans = max(ans, sum);
        }
        return ans;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maximumUniqueSubarraySum(nums []int) int {
    s := map[int]bool{}
    l, ans, sum := 0, 0, 0
    for r := 0; r < len(nums); r++ {
        for s[nums[r]] {
            s[nums[l]] = false
            sum -= nums[l]
            l++
        }
        s[nums[r]] = true
        sum += nums[r]
        if sum > ans { ans = sum }
    }
    return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maximumUniqueSubarraySum(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int l = 0, ans = 0, sum = 0;
        for (int r = 0; r < nums.length; ++r) {
            while (s.contains(nums[r])) {
                s.remove(nums[l]);
                sum -= nums[l++];
            }
            s.add(nums[r]);
            sum += nums[r];
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun maximumUniqueSubarraySum(nums: IntArray): Int {
        val s = mutableSetOf<Int>()
        var l = 0
        var ans = 0
        var sum = 0
        for (r in nums.indices) {
            while (nums[r] in s) {
                s.remove(nums[l])
                sum -= nums[l]
                l++
            }
            s.add(nums[r])
            sum += nums[r]
            ans = maxOf(ans, sum)
        }
        return ans
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def maximum_unique_subarray_sum(nums: list[int]) -> int:
    s: set[int] = set()
    l = ans = sum_ = 0
    for r, x in enumerate(nums):
        while x in s:
            s.remove(nums[l])
            sum_ -= nums[l]
            l += 1
        s.add(x)
        sum_ += x
        ans = max(ans, sum_)
    return ans
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn maximum_unique_subarray_sum(nums: Vec<i32>) -> i32 {
        use std::collections::HashSet;
        let mut s = HashSet::new();
        let (mut l, mut ans, mut sum) = (0, 0, 0);
        for r in 0..nums.len() {
            while s.contains(&nums[r]) {
                s.remove(&nums[l]);
                sum -= nums[l];
                l += 1;
            }
            s.insert(nums[r]);
            sum += nums[r];
            ans = ans.max(sum);
        }
        ans
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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