Skip to content

2461. Maximum Sum of Distinct Subarrays With Length K

#312

Problem link

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

Problem Summary

k 길이의 부분 배열 중에 원소가 전부 다를 때의 합의 최댓값을 구하는 문제

Solution

간단한 슬라이딩 윈도우 문제.
원소 하나씩 보면서 counter 하면서 모두 distinct 이면 결과에 업데이트 해주면 된다.

Source Code

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        result = 0
        c = Counter(nums[0 : k - 1])
        s = sum(nums[0 : k - 1])

        for i in range(k - 1, len(nums)):
            s += nums[i]
            c[nums[i]] += 1

            if len(c) == k:
                result = max(result, s)

            if c[nums[i - k + 1]] == 1:
                del c[nums[i - k + 1]]
            else:
                c[nums[i - k + 1]] -= 1
            s -= nums[i - k + 1]

        return result