Show problems as
Classic problem #2461MediumArrayHash TableSliding Window

Maximum Sum of Distinct Subarrays With Length K

Real-world version: Richest Run of Distinct Readings
Tracked in this browser only
Read Maximum Sum of Distinct Subarrays With Length K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A flow meter writes one reading per minute into the log nums, oldest reading first. An auditor wants to grade a stretch of exactly k consecutive minutes.

A stretch is auditable when no reading inside it repeats, that is, all k readings in the stretch are different from one another. The score of a stretch is the sum of its k readings.

Return the largest score over all auditable stretches. If the log contains no auditable stretch at all, return 0.

Examples

Example 1

Input
nums = [4, 9, 4, 6, 2, 9], k = 3
Output
19

The stretch of minutes 2 through 4 holds the readings 9, 4 and 6, which are all different, and they add up to 19. No other auditable stretch of three minutes scores higher.

Example 2

Input
nums = [7, 7, 7, 7], k = 2
Output
0

Every stretch of two minutes holds the same reading twice, so no stretch is auditable and the answer is 0.

Example 3

Input
nums = [8, 8, 1, 8, 8], k = 2
Output
9

The stretches 8,1 and 1,8 are auditable and both score 9; the stretches 8,8 are not.

Constraints

  • 1 <= k <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • The largest possible score is 10^10, so every answer fits comfortably in a 64-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_subarray_sum(nums: list[int], k: int) -> int:
Java
public long maximumSubarraySum(int[] nums, int k)

More on the same topics