2461. Maximum Sum of Distinct Subarrays With Length K

Problem : https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/

Difficulty : Medium

Status : Solved

Time : 00:00:00

---

---

풀이

간단하긴 한데, 어떻게 더 최적화할지를 생각해보게 되는 문제.

기본적으로는 딕셔너리를 사용하여 distinct한 숫자를 관리하면 된다. k개의 fix된 길이니 슬라이딩 윈도우를 수행하며 조건에 맞을 때마다 정답을 갱신하면 되겠다.

워낙 많이 보이는 타입의 문제다 보니, 최적화가 역시 관건이 될 것 같다.

풀이코드

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        numDict = defaultdict(int)
        ans = 0
        sums = 0
        d = 0

        for i, n in enumerate(nums) :
            numDict[n] += 1
            sums += n
            if numDict[n] == 1 :
                d += 1
                
            if i >= k :
                numDict[nums[i-k]] -= 1
                sums -= nums[i-k]
                if not numDict[nums[i-k]] :
                    d -= 1
            if d == k :
                ans = max(ans, sums)
        
        return ans