# 2841. Maximum Sum of Almost Unique Subarray

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: long long maxSum(vector& nums, int m, int k) { long long ans = 0; long 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def maxSum(self, nums: List[int], m: int, k: int) -> int: ans = 0 summ = 0 count = collections.Counter() for i, num in enumerate(nums): summ += num count[num] += 1 if i >= k: numToRemove = nums[i - k] summ -= numToRemove count[numToRemove] -= 1 if count[numToRemove] == 0: del count[numToRemove] if len(count) >= m: ans = max(ans, summ) return ans