Maximum Sum of Almost Unique Subarray Solution in Java

Problem Description

Welcome to the world of coding challenges! The “Maximum Sum of Almost Unique Subarray” problem is about maximizing your sum while ensuring that you don’t have too many duplicates. You are given an array of integers, and your task is to find the maximum sum of a subarray that contains at least m unique elements, with the additional constraint that the length of the subarray should not exceed k.

Think of it as gathering a diverse group of friends for a party, but you can only invite a limited number of them!

Code Solution


public class Solution {
  public long maxSum(List nums, int m, int k) {
    long ans = 0;
    long sum = 0;
    Map count = new HashMap<>();

    for (int i = 0; i < nums.size(); ++i) {
      sum += nums.get(i);
      count.merge(nums.get(i), 1, Integer::sum);
      if (i >= k) {
        final int numToRemove = nums.get(i - k);
        sum -= numToRemove;
        count.merge(numToRemove, -1, Integer::sum);
        if (count.get(numToRemove) == 0)
          count.remove(numToRemove);
      }
      if (count.size() >= m)
        ans = Math.max(ans, sum);
    }

    return ans;
  }
}

Approach

The approach taken in this solution involves keeping track of the sum of the current subarray while ensuring that you have at least m unique elements. As you iterate through the array, you add elements to your sum and count their occurrences. If you exceed the length k, you start removing elements from the beginning of the subarray. This way, you maintain the constraints while maximizing your sum.

Time and Space Complexity

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

Real-World Example

Imagine you are at a buffet with a variety of dishes. You want to try as many different dishes as possible (unique elements) without overloading your plate (length constraint). You can only take a limited number of dishes (k), but you want to maximize the deliciousness (sum) of what you can eat. This problem is all about finding that perfect balance!