2461. Maximum Sum of Distinct Subarrays With Length K

2461. Maximum Sum of Distinct Subarrays With Length K

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

The length of the subarray is k, and
All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

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

---

1. nums 를 순회하며 k 개의 연속된 숫자의 합을 구합니다

2. 연속된 숫자에서 동일한 숫자가 존재하는 경우 포기합니다

3. 가장 큰 합을 구합니다

 

가장 직관적인 방법으로 계산했습니다.

 

다만, 연속된 숫자에서 중복되는 숫자가 존재하는 경우 조합이 성립하지 않아 위 경우의 slice ( window ) 는 바로 제외할 수 있습니다. 이를 통해 조금 더 연산 갯수를 줄일 수 있습니다.

1. begin, end 의 기준 ( index ) 를 두고 'end - begin + 1' 의 값이 'k' 가 되는 경우가 조합이 됩니다

2. 새로운 index 값이 set ( 중복을 허용하지 않는 DS ) 에 이미 존재하는 경우, 중복되지 않는 위치까지 begin 을 end 까지 당길 수 있습니다

3. 존재하지 않는 경우 end 를 당기고 조합이 되는 지 확인하여 max 값을 갱신합니다

---

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumSubarraySum = function (nums, k) {
    var max = 0;
    var sum = 0;

    var set = {}, error = {};

    for (var i = 0; i < k - 1; i++) {
        var v = nums[i];

        sum += v;
        set[v] = (set[v] || 0) + 1;
        if (set[v] > 1) error[v] = true;
    }

    for (var i = k - 1; i < nums.length; i++) {
        var v = nums[i];

        sum += v;
        set[v] = (set[v] || 0) + 1;
        if (set[v] > 1) error[v] = true;

        if (Object.keys(error).length == 0) {
            max = Math.max(max, sum);
        }

        var pv = nums[i - k + 1];
        sum -= pv;
        set[pv] -= 1;
        if (set[pv] == 1) {
            delete error[pv];
        }
    }

    return max;
};