2389. Самая длинная последовательность с суммой (Longest Subsequence With Limited Sum)
Задание.
Вам дается целочисленный массив nums длины n и целочисленный массив запросов queries длины m.
Верните массив answer длины m, где answer[i] – это максимальный размер подпоследовательности, который вы можете взять из nums таким образом, чтобы сумма его элементов была меньше или равна queries[i].
Подпоследовательность – это массив, который может быть получен из другого массива путем удаления некоторых элементов или вообще без них без изменения порядка остальных элементов.
Пример 1.
Входные данные: nums = [4,5,2,1], queries = [3,10,21]
Результат: [2,3,4]
Пояснение:
Мы отвечаем на запросы следующим образом:
- Подпоследовательность [2,1] имеет сумму, меньшую или равную 3. Можно доказать, что 2 -- это максимальный размер такой подпоследовательности, поэтому ответ [0] = 2.
- Подпоследовательность [4,5,1] имеет сумму, меньшую или равную 10. Можно доказать, что 3 -- это максимальный размер такой подпоследовательности, поэтому ответ [1] = 3.
- Подпоследовательность [4,5,2,1] имеет сумму, меньшую или равную 21. Можно доказать, что 4 -- это максимальный размер такой подпоследовательности, поэтому ответ [2] = 4.
Пример 2.
Входные данные: nums = [2,3,4,5], queries = [1]
Результат: [0]
Пояснение: Пустая подпоследовательность - это единственная подпоследовательность, сумма которой меньше или равна 1, поэтому ответ [0] = 0.
Решение.
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
}
};