Sliding window-> Max sum of distinct subarray
123456789101112131415161718192021222324252627282930313233343536373839
import java.util.*;
class Main {
public static int maxSumDistinctSubarray(int[] nums, int k) {
int n = nums.length;
int left = 0;
int currentSum = 0;
int maxSum = 0;
HashMap<Integer, Integer> freq = new HashMap<>(); // track counts of elements
for (int right = 0; right < n; right++) {
int num = nums[right];
freq.put(num, freq.getOrDefault(num, 0) + 1);
currentSum += num;
// shrink window if size exceeds k or duplicates exist
while (freq.get(num) > 1 || (right - left + 1) > k) {
int leftNum = nums[left];
freq.put(leftNum, freq.get(leftNum) - 1);
currentSum -= leftNum;
left++;
}
// if valid window of size k with distinct elements
if (right - left + 1 == k) {
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}
public static void main(String[] args) {
int nums[] = {1, 5, 4, 2, 9, 9, 9};
int k = 3;
System.out.println(maxSumDistinctSubarray(nums, k)); // should print 15 (from [5,4,6] or [4,2,9])
}
}
Java
INFO