[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K

https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/?envType=daily-question&envId=2024-11-19

leetcode - Maximum Sum of Distinct Subarrays With Length K

문제 유형: 슬라이딩 윈도우

문제 난이도: Medium

 

 

문제

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.

 

정수 배열 nums와 정수 k를 받는다.

k만큼의 길이를 가지고 모든 요소가 중복되지 않는 부분배열의 최대 합을 구하시오.

 

 

풀이

sum은 현재 윈도우의 누적합,

freq[i]는 i의 빈도를 저장하는 목적으로 있다.

중복요소의 개수를 추적하는 dup도 만든다.

배열을 순차적으로 순회하면서, freq[nums[i]]에 빈도를 업데이트한다. 만약 2가 된다면, 중복이 생기는 것이므로 dup을 1 추가한다.

만약 i가 k-1이상이라서, 현재 윈도우의 크기가 k가 되었다면, 동시에 dup이 0이라면, 최대 합을 업데이트한다.

그리고, 맨 뒤 요소를 제거할 것이다. sum에서 nums[i-k+1]을 없애고, freq에서도 1 낮춘다.

만약 이번에 freq가 1이 되었다면, dup을 1 낮춘다.

 

최종적인 최대값을 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long res = 0;
        int n = nums.size();
        vector<int> freq(100001, 0);
        long long sum = 0;
        int dup = 0;

        for(int i = 0; i < n; ++i) {
            freq[nums[i]]++;
            if(freq[nums[i]] == 2) dup++;
            sum += nums[i];
            if(i >= k-1) {
                if(dup == 0) res = max(res, sum);
                sum -= nums[i-k+1];
                freq[nums[i-k+1]]--;
                if(freq[nums[i-k+1]] == 1) dup--;
            }
        }

        return res;
    }
};