0593MediumArrayHash TableSliding Window

Richest Run of Distinct Readings

Tracked in this browser only

Trains the technique from

LeetCode 2461Maximum Sum of Distinct Subarrays With Length K

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_subarray_sum(nums: list[int], k: int) -> int:

Java

public long maximumSubarraySum(int[] nums, int k)

The intended approach

Time O(n): each reading enters and leaves the window once.Space O(k) for the dictionary, which never holds more than k keys.

Move a window of fixed width `k` one minute at a time. Alongside it keep a running sum and a dictionary counting how many copies of each reading the window currently holds. When a reading leaves the window its count drops and the key is deleted once the count hits zero, so the number of keys always equals the number of different readings inside. A window is auditable exactly when the key count reaches `k`, and its running sum is compared against the best seen so far.

Pythonentry point: maximum_subarray_sum

def maximum_subarray_sum(nums, k):
    # O(n) time, O(k) space. Slide a window of exactly k readings, keeping a
    # running total and a tally of how many times each reading sits inside it.
    # The window holds k different readings exactly when the tally has k keys.
    n = len(nums)
    if k > n:
        return 0
    tally = {}
    running = 0
    best = 0
    for right in range(n):
        running += nums[right]
        value = nums[right]
        tally[value] = tally.get(value, 0) + 1
        if right >= k:
            gone = nums[right - k]
            running -= gone
            tally[gone] -= 1
            if tally[gone] == 0:
                del tally[gone]
        if right >= k - 1 and len(tally) == k:
            if running > best:
                best = running
    return best

The obvious version

Take every starting minute in turn, copy out the k readings that follow, collect the different values in that copy with a linear membership scan, and if there are k of them add the copy up. Keep the largest total found.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_subarray_sum(nums, k):
    n = len(nums)
    best = 0
    for start in range(n - k + 1):
        block = nums[start:start + k]
        distinct = []
        for v in block:
            if v not in distinct:
                distinct.append(v)
        if len(distinct) == k:
            total = 0
            for v in block:
                total += v
            if total > best:
                best = total
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in