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.

Examples

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

Solution

Method 1 – Sliding Window with Hash Set

Intuition

To maximize the sum of a subarray with unique elements, we need to find continuous windows without repetitions, and among all these, choose the one with the largest possible sum.

Approach

We use the sliding window technique with a Set to track unique elements. We maintain two pointers (start and end) that define the window boundaries.

  • If nums[end] is not in the set, we add it and update the sum.
  • If it is repeated, we remove elements from the left of the window until nums[end] can be inserted without repetitions.
  • At each step, we update the maximum sum value.

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.
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        seen: set[int] = set()
        sum_ = 0
        max_ = float('-inf')
        for num in nums:
            if num > 0 and num not in seen:
                seen.add(num)
                sum_ += num
            max_ = max(max_, num)
        return sum_ if sum_ > 0 else max_
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxSum(vector<int>& nums) {
        unordered_set<int> seen;
        int sum = 0;
        int maxVal = INT_MIN;
        for (int num : nums) {
            if (num > 0 && seen.find(num) == seen.end()) {
                seen.insert(num);
                sum += num;
            }
            maxVal = max(maxVal, num);
        }
        return sum > 0 ? sum : maxVal;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maxSum(nums []int) int {
    seen := map[int]bool{}
    l, ans, sum := 0, 0, 0
    for r := 0; r < len(nums); r++ {
        for seen[nums[r]] {
            seen[nums[l]] = false
            sum -= nums[l]
            l++
        }
        seen[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

class Solution {
    int maxSum(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        int sum = 0;
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            if (num > 0 && seen.add(num)) {
                sum += num;
            }
            max = Math.max(max, num);
        }
        return (sum > 0) ? sum : max;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maxSum(nums: IntArray): Int {
        val seen = mutableSetOf<Int>()
        var sum = 0
        var maxVal = Int.MIN_VALUE
        for (num in nums) {
            if (num > 0 && seen.add(num)) {
                sum += num
            }
            maxVal = maxOf(maxVal, num)
        }
        return if (sum > 0) sum else maxVal
    }
}
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn max_sum(nums: Vec<i32>) -> i32 {
        use std::collections::HashSet;
        let mut seen = HashSet::new();
        let mut sum = 0;
        let mut max_val = i32::MIN;
        for &num in &nums {
            if num > 0 && seen.insert(num) {
                sum += num;
            }
            max_val = max_val.max(num);
        }
        if sum > 0 { sum } else { max_val }
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maxSum(nums: number[]): number {
        const seen = new Set<number>()
        let sum = 0
        let maxVal = Number.NEGATIVE_INFINITY
        for (const num of nums) {
            if (num > 0 && !seen.has(num)) {
                seen.add(num)
                sum += num
            }
            maxVal = Math.max(maxVal, num)
        }
        return sum > 0 ? sum : maxVal
    }
}

Method 2 – Counting Unique Positive Numbers

Intuition

At first glance, the problem seems suited for a sliding window approach, as it asks for a maximum subarray sum.

However, the key insight is that since we can delete any elements, we should simply keep all unique positive numbers. This guarantees the largest possible sum, as negative numbers and duplicates only reduce the total. For example, given [1,2,-1,-2,1,0,-1], we can remove all negatives, then keep only one of each positive, resulting in [1,2,0] and a sum of 3.

Approach

  • If the array has only one element, return it directly.
  • Check if all numbers are negative; if so, return the largest (least negative) number.
  • Use a set to collect all unique positive numbers.
  • Sum these unique positive numbers and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int max_one = *max_element(nums.begin(), nums.end());
        if (max_one < 0) return max_one;
        unordered_set<int> uniquePositives;
        int maxSum = 0;
        for (int num : nums) {
            if (num > 0 && uniquePositives.find(num) == uniquePositives.end()) {
                uniquePositives.insert(num);
                maxSum += num;
            }
        }
        return maxSum;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxSum(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int max_one = Arrays.stream(nums).max().getAsInt();
        if (max_one < 0) {
            return max_one;
        }
        Set<Integer> uniquePositives = new HashSet<>();
        int maxSum = 0;
        for (int num : nums) {
            if (num > 0 && !uniquePositives.contains(num)) {
                uniquePositives.add(num);
                maxSum += num;
            }
        }
        return maxSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun maxSum(nums: IntArray): Int {
        if (nums.size == 1) return nums[0]
        val maxOne = nums.maxOrNull() ?: Int.MIN_VALUE
        if (maxOne < 0) return maxOne
        val uniquePositives = mutableSetOf<Int>()
        var maxSum = 0
        for (num in nums) {
            if (num > 0 && uniquePositives.add(num)) {
                maxSum += num
            }
        }
        return maxSum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        max_one = max(nums)
        if max_one < 0:
            return max_one
        unique_positives = set()
        max_sum = 0
        for num in nums:
            if num > 0 and num not in unique_positives:
                unique_positives.add(num)
                max_sum += num
        return max_sum
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn max_sum(nums: Vec<i32>) -> i32 {
        if nums.len() == 1 {
            return nums[0];
        }
        let max_one = *nums.iter().max().unwrap();
        if max_one < 0 {
            return max_one;
        }
        use std::collections::HashSet;
        let mut unique_positives = HashSet::new();
        let mut max_sum = 0;
        for &num in &nums {
            if num > 0 && unique_positives.insert(num) {
                max_sum += num;
            }
        }
        max_sum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    maxSum(nums: number[]): number {
        if (nums.length === 1) return nums[0]
        const maxOne = Math.max(...nums)
        if (maxOne < 0) return maxOne
        const uniquePositives = new Set<number>()
        let maxSum = 0
        for (const num of nums) {
            if (num > 0 && !uniquePositives.has(num)) {
                uniquePositives.add(num)
                maxSum += num
            }
        }
        return maxSum
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array and check/set membership in O(1) time per element.
  • 🧺 Space complexity: O(n), for storing up to n unique positive numbers in the set.