 # 2841. Maximum Sum of Almost Unique Subarray

Updated: 2023-09-04 LeetCode Problem 2841

## Problem Statement

You are given an integer array nums and two positive integers m and k.

The task is to return the maximum sum out of all almost unique subarrays of length k of nums. If no such subarray exists, return 0.

A subarray is almost unique if it contains at least m pairwise distinct elements.

## Naive Solution

A naive solution would be to generate all the possible subarrays of length k and check each one to see if it is almost unique and what its sum is. This would involve nested loops and would not be efficient.

## Hints & Tips

1. Use sliding window technique to find subarrays of length k.
2. Keep track of unique elements using a set.

## Approach

The solution adopts a sliding window approach to go through the given array nums, checking each subarray of size k for its “almost uniqueness” and sum.

## Steps

1. Define a helper function, is_unique, which will take a subarray and return whether it contains at least m distinct elements or not.

2. Initialize a variable _max to keep track of the maximum sum among the almost unique subarrays.

3. Loop through nums using the sliding window technique:

• Use the is_unique function to check if the current subarray is almost unique.
• Update _max with the maximum sum found so far.
4. Return _max if it is not 0; otherwise, return 0.

## Solution

def maxSum(nums: List[int], m: int, k: int) -> int:
n = len(nums)

def is_unique(arr, start, end, m):
distinct_elements = set(arr[start:end])
return len(distinct_elements) >= m

_max = 0
for i in range(n - k + 1):
if is_unique(nums, i, i + k, m):
_max = max(_max, sum(nums[i:i + k]))

return _max if _max != 0 else 0