Question:
Hello. An array A of N natural numbers is given. We need to find the size of a subarray A of maximum length, the sum of elements of which does not exceed K .
Example:
A = [1, 4, 2, 3]
K = 6
Ответ: 3 (подмассив [1, 2, 3])
Am I right in thinking that if the array is sorted, then the answer will be the number of the first elements of the array, the sum of which does not exceed К ? And is there a better way?
Answer:
If your interpretation of the problem statement is indeed correct, then the algorithm proposed to you is correct. However, a more efficient solution can be proposed.
You can use the normal quick sort algorithm with some modifications.
-
If after partitioning it turns out that the sum of the elements in the left (smaller) part of the array is not less than
K, then the right part of the array is no longer of interest to you and there is no point in wasting time on further sorting the right part. -
In the case when the sum of the elements in the left (smaller) part of the array is less than
K, you immediately know that all elements of the left part are certainly included in the desired subarray and there is no point in wasting time on further sorting the left part.
This is the same strategy as the classic "k smallest elements" algorithm, with the only difference being that you are not looking for k smallest elements, but an unknown number of smallest elements whose sum does not exceed K .
Thus, at each level of a recursive subdivision, you only need to recursively call one half of the subdivision, while the other half is either completely ignored or simply exited in its entirety (and then ignored). Such an algorithm should easily allow a true cyclic implementation, without the use of a stack.