# 2389. Longest Subsequence With Limited Sum
###### tags: `Leetcode` `Easy` `Binary Search`
Link: https://leetcode.com/problems/longest-subsequence-with-limited-sum/
## 思路 $O(mlogn+nlogn)$ $O(n)$
n = nums.size(), m = queries.size()
1. sort nums array
2. compute the prefix sum of nums array
3. binary search to find the first element larger than query, that is the answer
## Code

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        for(int i=1; i<n; i++) nums[i] += nums[i-1];
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            ans[i] = binarySearch(nums, queries[i]);
        }
        return ans;
    }
    private int binarySearch(int[] nums, int q){
        int l = 0;
        int r = nums.length;
        while(l<r){
            int mid = l+(r-l)/2;
            if(nums[mid]<=q) l = mid+1;
            else r = mid;
        }
        return l;
    }
}