LeetCode 2389: Longest Subsequence With Limited Sum

Explanation

To solve this problem, we can use dynamic programming. We will iterate through each query and for each query, we will iterate through the nums array to find the maximum size of subsequence with sum less than or equal to the query limit. We will keep track of the maximum size for each query and return the results.

• Sort the nums array to optimize the process.
• Initialize an array to store the maximum sizes for each query.
• Iterate through each query and for each query, iterate through the sorted nums array to find the maximum size of subsequence.
• Use dynamic programming to keep track of the maximum size.

Time complexity: O(n * m * log(n)) where n is the length of nums array and m is the length of queries array. Space complexity: O(n) where n is the length of nums array.

import java.util.Arrays;

class Solution {
    public int[] maxSubsequenceSizes(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] result = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int sum = 0;
            int size = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += nums[j];
                if (sum <= queries[i]) {
                    size++;
                } else {
                    break;
                }
            }
            result[i] = size;
        }

        return result;
    }
}