Watch 10 video solutions for Maximum Unique Subarray Sum After Deletion, a easy level problem involving Array, Hash Table, Greedy. This walkthrough by codestorywithMIK has 6,191 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Return the maximum sum of such a subarray.
Example 1:
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:
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:
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] <= 100Problem Overview: You are given an array of integers. You can delete elements so the remaining subarray contains only unique values. The goal is to maximize the sum of that subarray. The challenge is ensuring uniqueness while keeping the sum as large as possible.
Approach 1: Brute Force Enumeration (O(n²) time, O(n) space)
Check every possible subarray and verify whether all elements are unique. For each starting index, expand the subarray while tracking elements in a HashSet. If a duplicate appears, stop expanding that window. Maintain the running sum and update the maximum whenever the subarray remains unique. This approach is straightforward but inefficient because every start index may scan the rest of the array.
Approach 2: Greedy + Hash Table Sliding Window (O(n) time, O(n) space)
Use a sliding window with two pointers and a HashSet to track elements currently inside the window. Iterate the right pointer across the array while adding values to the running sum. If a duplicate appears, move the left pointer forward and remove elements from the set until the duplicate disappears. This effectively simulates deleting elements from the current window to restore uniqueness. Each element enters and leaves the window at most once, giving linear time complexity.
The greedy insight is that a valid window must contain only unique values. When a duplicate appears, shrinking the window from the left is always optimal because it removes the earliest conflicting element while preserving as much of the current sum as possible. The algorithm continuously maintains the best unique-sum window.
This technique is a standard pattern combining Hash Table lookups with the Array sliding window technique. Many interview problems involving distinct elements or maximum window sums rely on the same idea. The greedy decision of removing elements only when duplicates appear keeps the window valid while exploring all candidates efficiently. Similar patterns appear in problems involving Greedy optimization and distinct-element constraints.
Recommended for interviews: The sliding window with a hash table is the expected solution. The brute force version demonstrates the baseline idea of checking uniqueness, but the O(n) window approach shows you understand how to maintain constraints dynamically while scanning the array.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with HashSet | O(n²) | O(n) | Useful for understanding the uniqueness constraint and validating smaller inputs |
| Greedy Sliding Window + Hash Table | O(n) | O(n) | Optimal approach for large arrays and typical interview solution |