2841. Maximum Sum of Almost Unique Subarray Medium

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

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

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

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:
Input: nums = [2,6,7,3,1,7], m = 3, k = 4
Output: 18
Explanation: There are 3 almost unique subarrays of size k = 4. These subarrays are [2, 6, 7, 3], [6, 7, 3, 1], and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3] which has a sum of 18.

Example 2:
Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3
Output: 23
Explanation: There are 5 almost unique subarrays of size k. These subarrays are [5, 9, 9], [9, 9, 2], [9, 2, 4], [2, 4, 5], and [4, 5, 4]. Among these subarrays, the one with the maximum sum is [5, 9, 9] which has a sum of 23.

Example 3:
Input: nums = [1,2,1,2,1,2,1], m = 3, k = 3
Output: 0
Explanation: There are no subarrays of size k = 3 that contain at least m = 3 distinct elements in the given array [1,2,1,2,1,2,1]. Therefore, no almost unique subarrays exist, and the maximum sum is 0.

Approach

Input: An integer array nums and two positive integers m and k

Output: Return the maximum sum of a contiguous subarray where the array length strictly adheres to k elements wide and contains >= m uniquely distinguished separate elements collectively.

This problem targets Fixed-length Sliding Window algorithms.

Because the window's breadth statically maps values strictly exactly k wide, the complexity hurdle involves counting specific unrepeated objects individually ensuring >= m independent variables encompass the active interval, allowing only those hitting qualification standards counting towards our total maximum valid subarray sums calculated consistently.

Consequently, HashMap frequencies (freq) track local values appearing within sliding array spans logically.

Begin scanning from index 0 mapping outward widths advancing element increments sequentially linearly up to limit k, triggering compression bounds dropping furthest trailing left node properties updating respective value tallies appropriately scaling forwards structurally ensuring dimension maintenance consistently mapped precisely tight mathematically perfectly dynamically.

Each valid phase evaluates active intervals scaling size parameters equating tightly against fixed lengths k with distinctive objects reaching threshold >= m, registering best value combinations iteratively.

Implementation

python

from typing import List

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        # Dictionary registering internal sliding bounds frequency occurrences respectively
        freq = {}
        # Max limit metric initialized tracking bounds evaluating structural properties 
        max_sum = 0
        # Initialize bounds scaling start index structurally leftwards originally 
        left = 0
        # Initial composite totals variable mapping sliding array constraints
        window_sum = 0
        
        # Iteration cycle spanning variables propagating structurally extending sequences rightwards consistently   
        for right in range(len(nums)):
            num = nums[right]
            # Accumulate overall boundary summations dynamically
            window_sum += num
            # Update metric dictionaries charting active properties dynamically over map layouts  
            freq[num] = freq.get(num, 0) + 1
            
            # Collapse excessive subsets extending beyond structural array thresholds mathematically  
            if right - left + 1 > k:
                left_num = nums[left]
                # Scale bounds recalculating aggregate sums respectively
                window_sum -= left_num
                # Retract frequencies eliminating outdated parameters correctly mapped backwards
                freq[left_num] -= 1
                # Wipe redundant mappings retaining optimization speed efficiently
                if freq[left_num] == 0:
                    del freq[left_num]
                # Offset scaling advancing boundary points forwards correctly
                left += 1
            
            # Subarray metric verification crosschecks evaluating target constraints properly aligning results  
            if right - left + 1 == k and len(freq) >= m:
                max_sum = max(max_sum, window_sum)
        
        return max_sum

javascript

/**
 * @param {number[]} nums
 * @param {number} m - minimum distinct elements requirement bounding subsets uniquely
 * @param {number} k - strict subarray scaling boundaries dimensions lengths fixedly
 * @return {number}
 */
var maxSum = function(nums, m, k) {
    let left = 0;
    let total = 0;
    let maxSum = 0;
    const freq = new Map();

    for (let right = 0; right < nums.length; right++) {
        const num = nums[right];
        total += num;
        freq.set(num, (freq.get(num) || 0) + 1);

        // Adjust constraints ensuring arrays map accurately bounded tightly to parameters logically
        if (right - left + 1 > k) {
            const leftNum = nums[left];
            total -= leftNum;
            freq.set(leftNum, freq.get(leftNum) - 1);
            if (freq.get(leftNum) === 0) freq.delete(leftNum);
            left++;
        }

        // Output calculation registering successful bounds crossing targets
        if (right - left + 1 === k && freq.size >= m) {
            maxSum = Math.max(maxSum, total);
        }
    }

    return maxSum;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(k) holding array elements spanning frequencies uniformly mapping hash mappings bounded strictly within length size limits parameter intervals.

Links

2841. Maximum Sum of Almost Unique Subarray (English)2841. 几乎唯一子数组的最大和 (Chinese)