Maximum Sum Subarray with At Most K Distinct Integers

Given an integer array nums and an integer k, your task is to find a contiguous subarray with the maximum possible sum, subject to the condition that it contains at most $$k$$ distinct integers. A subarray is a contiguous portion of the array. Note that if k is 0, the answer is 0 and the subarray is considered empty in terms of distinct elements, so the output should be 0.

Example: For nums = [1, 2, 1, 2, 3] and k = 2, one valid subarray is [1, 2, 1, 2] which has a sum of 6 and contains only 2 distinct integers. Hence, the answer is 6.

inputFormat

The input begins with an integer T, representing the number of test cases. Each test case comprises two lines:

• The first line contains two integers n and k, where n is the number of elements in the array and k is the maximum number of distinct integers allowed in the subarray.
• The second line contains n space-separated integers denoting the elements of nums.

outputFormat

For each test case, output one line with a single integer, which is the maximum possible sum of a contiguous subarray of nums that contains at most k distinct integers.

## sample

3
5 2
1 2 1 2 3
5 1
5 3 2 1 5
7 3
1 2 1 2 1 2 1

6
5
10

</p>