Show problems as
Classic problem #2099EasyArrayHash TableSortingHeap (Priority Queue)

Find Subsequence of Length K With the Largest Sum

Real-world version: Keeping the k Best Readings in Place
Tracked in this browser only
Read Find Subsequence of Length K With the Largest Sum on LeetCode(opens in a new tab)

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

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

Python
def max_subsequence(readings: list[int], k: int) -> list[int]:
Java
public int[] maxSubsequence(int[] readings, int k)

More on the same topics