K-Distinct Subarray Sum

Moderate

0/80

1 upvote

Problem statement

You are given an array of integers arr of size N and an integer K. Your task is to find the maximum sum of a contiguous subarray that contains at most K distinct elements.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains two space-separated integers, N (the size of the array) and K.
The second line contains N space-separated integers, representing the elements of the array arr.

Output Format:

The output should be a single long integer representing the maximum possible sum of a valid subarray.

Note:

A subarray is a contiguous part of an array.
A valid subarray is one that has K or fewer unique integer values.

If all possible subarray sums are negative, the answer should be the largest (closest to zero) of these negative sums.

Sample Input 1:

6 2
1 2 5 1 2 3

Sample Output 1:

Explanation for Sample 1:

The subarray [2, 5] has sum 7 and contains 2 distinct elements. The subarray [1, 2, 1, 2] has sum 6 and 2 distinct elements. The maximum is 7.

Expected Time Complexity:

The expected time complexity is O(N), where N is the size of the array.

Constraints:

1 <= K <= N <= 10^5
-10^9 <= arr[i] <= 10^9
Time limit: 1 sec

Approaches (1)

Approach 1

Hashing

Time Complexity

Space Complexity

(100% EXP penalty)

K-Distinct Subarray Sum

Console