Solution: Longest Subsequence With Limited Sum

Statement

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

For each element in queries, determine the maximum number of elements that can be selected from nums to form a subsequenceA subsequence is formed by removing zero or more elements from the array without changing the order of the remaining elements. such that the sum of the selected elements is less than or equal to the query value.

Return an array answer of length m, where answer[i] represents the size of the largest subsequence of nums whose sum is less than or equal to queries[i].

Constraints

• n $==$ nums.length

• m $==$ queries.length

• $1 \leq$ n, m $\leq 10^3$

• $1 \leq$ nums[i], queries[i] $\leq 10^5$

Solution

The algorithm begins by sorting the nums array in ascending order to facilitate efficient binary search operations. It then constructs a prefix sum array, where each element represents the cumulative sum of elements in nums up to that index. This allows quick and efficient calculation of the sum of any contiguous subsequence.

For each query, the algorithm uses a binary search on the prefix sum array to determine the maximum length of a subsequence whose sum is less than or equal to the query value. The binary search identifies the largest index where the cumulative sum does not exceed the query. All elements from the start of the array up to this index form the valid subsequence, and the index corresponds directly to its length.

The algorithm steps are as follows:

1. Sort the nums array in ascending order to ensure that smaller elements are considered first when constructing subsequences. This helps us form subsequences with minimal sums, making it easier to find valid subsequences for each query.

2. Construct a prefixSum array, where each element represents the cumulative sum of elements in nums up to that index. This allows quick calculation of the sum for any contiguous subsequence.

3. For each query, perform a binary search on the prefixSum array to find the maximum number of elements in nums whose sum does not exceed the query value. The binary search works as follows:

   1. Initialize two pointers: low at the start of the array and high at the end.

   2. Iterate while low <= high:

      1. Compute the midpoint: mid = (low + high) / 2.

      2. If prefixSum[mid] <= query, it indicates that a subsequence ending at mid is valid. Update low to mid + 1 to explore larger subsequences.

      3. Otherwise, update high to mid - 1 to search for smaller subsequences.

4. After the binary search, the low pointer indicates the largest valid subsequence length. All elements from the start of the array up to low - 1 form this subsequence, as their cumulative sum is less than or equal to the query value.

5. Append the value of low (representing the subsequence length) to the answer list.

6. After processing all queries, the answer list contains the lengths of the largest subsequences for each query. Return this answer list.

Let’s look at the following illustration to get a better understanding of the solution: