#2389

Longest Subsequence With Limited Sum

newbie · 255 · lc easy +19 · verified · 73.4% accepted · 2,132 likes · top 84%

Description

You are given an integer array nums of length n and an integer array queries of length m.

For each query queries[i], find the maximum length of a subsequence of nums whose elements sum to at most queries[i].

Return an array answer of length m where answer[i] holds the answer for the i^th query.

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]

Output: [2,3,4]

Explanation: We answer the queries as follows:

- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.

- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.

- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:

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

Output: [0]

Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Code

1

2

3

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]: