Show problems as
Classic problem #2389EasyArrayBinary SearchGreedySortingPrefix Sum

Longest Subsequence With Limited Sum

Real-world version: Parcels Within Each Allowance
Tracked in this browser only
Read Longest Subsequence With Limited Sum on LeetCode(opens in a new tab)

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

Parcel weights are given as nums, and each entry of queries is a weight allowance.

For each allowance, work out the largest number of parcels that can be chosen so their weights total at most that allowance. Parcels may be chosen from anywhere in the list.

Return those counts, one per allowance, in the order the allowances are given.

Examples

Example 1

Input
nums = [17, 4, 23, 9], queries = [30, 4, 3, 53]
Output
[3, 1, 0, 4]

Sorted, the weights run 4, 9, 17, 23 with running totals 4, 13, 30, 53. An allowance of 30 reaches three parcels, one of 4 reaches one, one of 3 reaches none, and one of 53 takes all four.

Example 2

Input
nums = [1, 1, 1, 1, 1], queries = [1, 2, 3, 4, 5, 6]
Output
[1, 2, 3, 4, 5, 5]

Every parcel weighs one, so each allowance fits that many parcels, capped at the five available.

Example 3

Input
nums = [100, 200, 300], queries = [50]
Output
[0]

Even the lightest parcel is over the allowance, so none fit.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= queries.length <= 1000
  • 1 <= nums[i] <= 10^6
  • 1 <= queries[i] <= 10^6

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 answer_queries(nums: list[int], queries: list[int]) -> list[int]:
Java
public int[] answerQueries(int[] nums, int[] queries)

More on the same topics