Maximum Sum Of Distinct Subarrays With Length K - Leetcode Solution

Problem Statement:

Given an array nums consisting of n integers, and an integer k. Find the maximum sum of distinct subarrays of length k.

Example 1: Input: nums = [1, 2, 1, 2, 3], k = 2 Output: 7 Explanation: Subarrays [1, 2] and [2, 3] are distinct and have maximum sum of 3 + 4 = 7.

Example 2: Input: nums = [1, 4, 2, 3, 5], k = 3 Output: 13 Explanation: Subarrays [1, 4, 2] and [4, 2, 3] are distinct and have maximum sum of 7 + 6 = 13.

Approach:

• We will use sliding window approach.
• Initialize a set and window sum.
• Traverse through the array using a sliding window.
• For each window, check if all the elements in the window are distinct.
• If all elements are distinct, calculate the window sum and add it to the answer.
• Else, remove the first element from the window and continue traversing.
• At the end, return the answer.

Code:

class Solution { public: int maxSumOfDistinctSubarrays(vector<int>& nums, int k) { int n = nums.size(); int ans = 0, cur_sum = 0; unordered_set<int> st; for(int i=0;i<n;i++){ if(i>=k&&st.find(nums[i-k])!=st.end()){ st.erase(nums[i-k]); cur_sum-=nums[i-k]; } if(st.find(nums[i])==st.end()){ st.insert(nums[i]); cur_sum+=nums[i]; } if(i>=k-1) ans = max(ans, cur_sum); } return ans; } };

Time Complexity: O(n) as we are just traversing the array once.

Space Complexity: O(k) as we are storing at most k elements in the set.

1