Maximum Sum of Almost Unique Subarray Solution in C++

Explore More Solutions

Problem Description

Ah, the “Maximum Sum of Almost Unique Subarray” problem! It’s like trying to find the perfect avocado in a grocery store—everyone wants it, but it’s always just out of reach. The task is to find a contiguous subarray of a given array of integers, where the sum of the elements is maximized, but with a twist: you can only have a limited number of unique elements in that subarray. Think of it as trying to throw a party with a guest list that has a strict limit on how many unique friends you can invite.

In simpler terms, given an array nums, you need to find the maximum sum of a subarray that contains at most m unique integers, and each unique integer can appear at most k times.

Code Solution


class Solution {
 public:
  long long maxSum(vector& nums, int m, int k) {
    long ans = 0;
    long sum = 0;
    unordered_map count;

    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      ++count[nums[i]];
      if (i >= k) {
        const int numToRemove = nums[i - k];
        sum -= numToRemove;
        if (--count[numToRemove] == 0)
          count.erase(numToRemove);
      }
      if (count.size() >= m)
        ans = max(ans, sum);
    }

    return ans;
  }
};

Approach Explanation

The code uses a sliding window technique combined with a hash map to keep track of the count of unique elements in the current window. As we iterate through the array, we maintain a running sum of the elements. If the number of unique elements exceeds m, we slide the window by removing elements from the left until we are back within the limit. The maximum sum is updated whenever the count of unique elements is valid.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(m)

Real-World Example

Imagine you’re at a buffet with a limited number of unique dishes you can try (let’s say 3). You want to maximize your enjoyment (sum of deliciousness) while ensuring you don’t exceed the limit of unique dishes. You might load up on your favorite pasta (up to k times), but you can’t just keep piling on the same dish forever. You have to balance your plate with a few other options to keep it interesting. This problem is all about finding that perfect balance!