You are given an integer array nums of length n, and an integer array queries of length m.
Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
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.
Constraints:
n == nums.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 106program main
implicit none
integer, parameter :: n = 4, m = 3
integer, dimension(n) :: nums = (/4, 5, 2, 1/)
integer, dimension(m) :: queries = (/3, 10, 21/)
integer, dimension(m) :: answer
call solve(nums, queries, answer)
write (*, '(A)') 'Answer:'
write (*, '(*(I0, 1X))') answer
contains
subroutine solve(nums, queries, answer)
implicit none
integer, intent(in) :: nums(:), queries(:)
integer, intent(out) :: answer(:)
integer :: i, j, k, l, m, n, q
integer :: max_size
logical :: found
do i = 1, m
max_size = 0
found = .false.
do j = 1, n
if (nums(j) <= queries(i)) then
do k = j + 1, n
if (nums(k) <= queries(i)) then
do l = k + 1, n
if (nums(l) <= queries(i)) then
do m = l + 1, n
if (nums(m) <= queries(i)) then
if (max_size < 4) then
max_size = 4
found = .true.
end if
else
exit
end if
end do
if (found) exit
end if
end do
if (found) exit
end if
end do
if (found) exit
end if
end do
answer(i) = max_size
end do
end subroutine solve
end program mainProgram received signal SIGSEGV: Segmentation fault - invalid memory reference. Backtrace for this error: #0 0x7d3415ce3960 in ??? #1 0x7d3415ce2ac5 in ??? #2 0x7d3415ad951f in ??? #3 0x5bf0e0c67440 in solve.0 #4 0x5bf0e0c6767e in MAIN__ #5 0x5bf0e0c6782f in main
module Main
implicit none
integer, parameter :: n = 4, m = 3
integer, dimension(n) :: nums = [4, 5, 2, 1]
integer, dimension(m) :: queries = [3, 10, 21]
integer, dimension(m) :: answer
contains
subroutine solve(nums, queries, answer)
implicit none
integer, dimension(n), intent(in) :: nums
integer, dimension(m), intent(in) :: queries
integer, dimension(m), intent(out) :: answer
! Local variables
integer :: i, j, k, l, sum, max_size
logical :: found
! Initialize the answer array
answer = 0
! Loop through each query
do i = 1, m
! Initialize the maximum size of the subsequence
max_size = 0
! Loop through each number in the array
do j = 1, n
! Initialize the sum of the subsequence
sum = 0
! Loop through each number in the subsequence
do k = j, n
! Calculate the sum of the subsequence
sum = sum + nums(k)
! Check if the sum is less than or equal to the query
if (sum <= queries(i)) then
! Update the maximum size of the subsequence
max_size = max(max_size, k - j + 1)
else
! Break out of the inner loop
exit
end if
end do
end do
! Update the answer array
answer(i) = max_size
end do
end subroutine solve
end module Main
program main
use Main
implicit none
! Call the solve function
call solve(nums, queries, answer)
! Print the answer array
write (*, "(4(i0, 1x))") answer
end program main
temp.f95:59:12:
1 | module Main
| 2
......
59 | program main
| 1
Error: Global name ‘main’ at (1) is already being used as a MODULE at (2)
temp.f95:60:9:
60 | use Main
| 1
Error: ‘main’ of module ‘main’, imported at (1), is also the name of the current program unit
from bisect import bisect
def maxSizeSubsequenceSumQueries(nums, queries):
nums.sort()
prefixSums = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
prefixSums[i + 1] = prefixSums[i] + x
answer = []
for q in queries:
idx = bisect(prefixSums, q)
answer.append(idx - 1)
return answer
The algorithm sorts the nums array in ascending order, then calculates the prefix sums for easy sum checks. For each query, it finds the position for the query in the prefix sums array using binary search, and the index of that position minus one represents the maximum size of a subsequence whose sum is less than or equal to the query. It adds that value to the answer array.
#include <vector>
#include <algorithm>
#include <numeric>
std::vector<int> maxSizeSubsequenceSumQueries(std::vector<int>& nums, std::vector<int>& queries) {
std::sort(nums.begin(), nums.end());
std::vector<int> prefixSums(nums.size() + 1);
std::partial_sum(nums.begin(), nums.end(), prefixSums.begin() + 1);
std::vector<int> answer(queries.size());
for (int i = 0; i < queries.size(); ++i) {
answer[i] = std::upper_bound(prefixSums.begin(), prefixSums.end(), queries[i]) - prefixSums.begin() - 1;
}
return answer;
}
The algorithm sorts the nums array in ascending order, then calculates the prefix sums for easy sum checks. For each query, it finds the position for the query in the prefix sums array using binary search, and the index of that position minus one represents the maximum size of a subsequence whose sum is less than or equal to the query. It adds that value to the answer array.