1119EasyArrayHash TableSortingHeap (Priority Queue)

Keeping the k Best Readings in Place

Tracked in this browser only

Trains the technique from

LeetCode 2099Find Subsequence of Length K With the Largest Sum

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 row of readings is given, and k of them are to be kept so that their total is as large as possible.

Several choices can tie on total, so the choice is pinned down like this: rank the positions of the row by their reading, largest first, and settle any tie in favour of the earlier position. Keep the first k positions of that ranking.

Return the kept readings in the order their positions appear in the row.

Examples

Example 1

Input: readings = [1, 9, 2, 8, 3, 7], k = 3
Output: [9, 8, 7]

The three largest readings are 9, 8 and 7, and they are reported in the order the row holds them.

Example 2

Input: readings = [2, 5, 2], k = 2
Output: [2, 5]

The largest reading is 5 and one of the two readings of 2 joins it. The tie goes to the earlier of the two, so the report reads 2 then 5.

Example 3

Input: readings = [-5, -4, -3], k = 1
Output: [-3]

Only one reading is kept, and the largest of the three sits at the end of the row.

Constraints

1 <= readings.length <= 1000
-10^5 <= readings[i] <= 10^5
1 <= k <= readings.length

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 max_subsequence(readings: list[int], k: int) -> list[int]:

Java

public int[] maxSubsequence(int[] readings, int k)

The intended approach

Time O(n log n) for the ranking.Space O(n) for the ranking and the answer.

Keeping the `k` largest readings gives the largest total, and nothing about the row's order can change that: swapping any kept reading for a larger unkept one only raises the total. So rank the positions rather than the readings themselves, ordering by falling reading with the position itself as the tie-breaker, which is exactly the rule the answer asks for. Take the first `k` positions of that ranking, put those positions back into increasing order, and read off the row at them. Holding on to positions rather than values is what makes the final ordering possible, since equal readings would otherwise be indistinguishable and the report could come out in the wrong arrangement.

Pythonentry point: max_subsequence

def max_subsequence(readings, k):
    ranked = sorted(range(len(readings)), key=lambda i: (-readings[i], i))
    kept = sorted(ranked[:k])
    return [readings[i] for i in kept]

The obvious version

List every choice of `k` positions, add up each one's readings, and hold on to the best total, settling a tie in favour of the choice whose positions come first. Then read the row at the winning positions. Costs the number of ways of choosing `k` positions from the row.

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_max_subsequence(readings, k):
    from itertools import combinations
    best = None
    kept = None
    for spots in combinations(range(len(readings)), k):
        total = 0
        for i in spots:
            total += readings[i]
        if best is None or total > best or (total == best and spots < kept):
            best = total
            kept = spots
    return [readings[i] for i in kept]

How this problem was checked

Reference solution executed against 15 test cases — 15 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