3487. Maximum Unique Subarray Sum After Deletion

Problem Description

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:

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

Return the maximum sum of such a subarray.

Intuition

To solve the problem, we take a greedy approach combined with the use of a hash table.

Firstly, identify the maximum value mx within the array. If mx is less than or equal to 0, the best outcome attainable with a non-empty subarray is simply choosing the maximum element from the array. This is because any sum of positive numbers must be greater than or equal to negative or zero-valued numbers.

In the scenario where mx is greater than 0, it indicates the presence of positive numbers. Our task then is to maximize the sum by selecting only the distinct, positive integers. We can achieve this by iterating through nums, utilizing a hash table to ensure all elements in our chosen subarray are unique, and accumulating their sum to find the maximum possible value.

Learn more about Greedy patterns.

Solution Approach

The solution utilizes a Greedy strategy with a Hash Table to efficiently solve the problem.

Identify the Maximum Value: Start by finding the maximum value mx in the array nums.
- If mx is less than or equal to 0, return mx immediately. This is because any positive subarray sum will always be better than or equal to non-positive numbers.
Initialize Variables:
- ans to store the maximum sum found.
- s as a hash set to keep track of unique elements that have been added to the sum.
Traverse the Array:
- Iterate over each element x in nums.
- If x is negative or already exists in the set s, skip it to maintain unique, positive elements.
- If x is positive and not in s, add x to ans and insert x into the set s to ensure uniqueness.

This approach ensures that we compile a maximum sum using unique elements in linear time, efficiently employing the set to handle duplicates.

The final result, stored in ans, will be the desired maximum sum of a subarray with unique elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach:

Consider the input array nums = [3, -1, 3, 5, -2, 5, 6].

Identify the Maximum Value:
- The maximum value mx in the array is 6. Since 6 is greater than 0, we proceed to find the maximum sum of unique elements.
Initialize Variables:
- Set ans = 0 to store the sum of unique elements.
- Initialize an empty set s to keep track of the unique elements.
Traverse the Array:
- First element 3 is positive and not in s. Add 3 to ans (now ans = 3) and insert 3 into s (now s = {3}).
- Second element -1 is negative, so skip it.
- Third element 3 already exists in s, skip it to maintain uniqueness.
- Fourth element 5 is positive and not in s. Add 5 to ans (now ans = 8) and insert 5 into s (now s = {3, 5}).
- Fifth element -2 is negative, skip it.
- Sixth element 5 already exists in s, skip it.
- Seventh element 6 is positive and not in s. Add 6 to ans (now ans = 14) and insert 6 into s (now s = {3, 5, 6}).

The loop completes and the maximum sum of a subarray with unique elements is stored in ans, which is 14. Thus, the maximum sum is 14.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxSum(self, nums: List[int]) -> int:
5        # Find the maximum number in the list
6        max_value = max(nums)
7      
8        # If the maximum value is less than or equal to zero, return it since including any other element won't increase the sum
9        if max_value <= 0:
10            return max_value
11      
12        # Initialize a variable to store the answer
13        result = 0
14      
15        # Use a set to track the unique elements we have already added to the result
16        unique_elements = set()
17      
18        # Iterate over each element in the list
19        for num in nums:
20            # Skip negative numbers and numbers we've already added
21            if num < 0 or num in unique_elements:
22                continue
23          
24            # Add the current number to the result and mark it as added
25            result += num
26            unique_elements.add(num)
27      
28        return result
29

1import java.util.Arrays;
2
3class Solution {
4    public int maxSum(int[] nums) {
5        // Find the maximum value in the array
6        int max = Arrays.stream(nums).max().getAsInt();
7      
8        // If the maximum value is less than or equal to 0, return it
9        if (max <= 0) {
10            return max;
11        }
12      
13        // Boolean array to keep track of numbers that have been added to the sum
14        boolean[] seen = new boolean[201]; // Assuming numbers are within the range of 0 to 200
15        int result = 0; // Initialize the sum
16      
17        // Iterate through each number in the array
18        for (int num : nums) {
19          
20            // If the number is negative or has already been added, skip it
21            if (num < 0 || seen[num]) {
22                continue;
23            }
24          
25            // Add the number to the sum and mark it as seen
26            result += num;
27            seen[num] = true;
28        }
29      
30        // Return the calculated sum
31        return result;
32    }
33}
34

1#include <vector>
2#include <unordered_set>
3#include <algorithm> // For std::max_element
4
5class Solution {
6public:
7    // Method to find the maximum sum of unique positive numbers in the vector
8    int maxSum(std::vector<int>& nums) {
9        // Find the maximum value in nums. Use std::max_element instead of non-standard features.
10        int maxVal = *std::max_element(nums.begin(), nums.end());
11      
12        // If all numbers are non-positive, return the maximum value (which would be the least negative or zero).
13        if (maxVal <= 0) {
14            return maxVal;
15        }
16
17        // Create an unordered set to track unique numbers we've added to the sum
18        std::unordered_set<int> uniqueNumbers;
19        int totalSum = 0; // Variable to store the sum of unique positive numbers
20
21        // Iterate through each number in the vector
22        for (int num : nums) {
23            // Skip negative numbers and numbers already added to the sum
24            if (num < 0 || uniqueNumbers.count(num) > 0) {
25                continue;
26            }
27
28            // Add the unique positive number to the sum
29            totalSum += num;
30            // Insert the number into the set to ensure it's only added once
31            uniqueNumbers.insert(num);
32        }
33
34        return totalSum; // Return the computed sum
35    }
36};
37

1function maxSum(nums: number[]): number {
2    // Find the maximum value in the array
3    const maxElement = Math.max(...nums);
4
5    // If the maximum value is less than or equal to zero, return it
6    if (maxElement <= 0) {
7        return maxElement;
8    }
9
10    // Create a set to track elements that have been added to the sum
11    const uniqueElementsSet = new Set<number>();
12  
13    // Initialize the sum to zero
14    let sum: number = 0;
15
16    // Iterate through the array
17    for (const number of nums) {
18        // If the number is negative or already added, skip it
19        if (number < 0 || uniqueElementsSet.has(number)) {
20            continue;
21        }
22      
23        // Add the number to the sum
24        sum += number;
25
26        // Add the number to the set to mark it as added
27        uniqueElementsSet.add(number);
28    }
29
30    // Return the computed sum
31    return sum;
32}
33

Time and Space Complexity

The time complexity of the code is O(n) because we iterate through the list nums once to find the maximum element and a second time to accumulate the sum of unique positive numbers. The space complexity is O(n) because we use a set s to store up to all unique elements from nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know