Hello. Given an array A of N natural numbers. It is necessary to find the size of the subarray A maximum length, the sum of the elements of which does not exceed K

Example:

 A = [1, 4, 2, 3] K = 6 Ответ: 3 (подмассив [1, 2, 3])

Do I think correctly that if you sort the array, the answer will be the number of first array elements, the sum of which does not exceed К ? And is there a better way?

  • It seems to be so, but only if you do not ask the subarray as a segment of consecutive elements of the existing array - then in your case it will be 2 (elements 4, 2). Then it is a completely different task. - Harry
  • The sequence is not important. I wrote a comment to the answer @ioann sys, with an attempt to prove the correctness of the decision, but could be mistaken in reasoning. I would be grateful if you look. - Nikolai Petrov
  • @ Nikolay Petrov, yes, that's right. You take such a subarray, replace any element in it with some other of the original array — the amount increases, since minimal elements are already collected in your subarray. Only now the sum can still remain less than K, that is, there may be more than one subarray. Then it is more logical to set the length problem, since they will have the same length, since replacing one of the elements with a longer length cannot be increased, only reduced or retained, and this sub-array is no longer suitable. - user239133

2 answers 2

If your interpretation of the problem statement is indeed correct, then the algorithm proposed to you is correct. However, a more effective solution can be proposed.

You can apply an ordinary quick sort algorithm with an additional modification.

  • 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 no longer interests you and there is no point in wasting time 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 the elements of the left part are obviously part of the desired subarray and there is no point in wasting time further sorting the left part.

This is the same strategy that the classic "k smallest elements" search algorithm works with, with the only difference 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 the recursive subdivision, you need to perform a recursive call for only one half of the subdivision, while the second half is either completely ignored, or just completely sent to the output (and then ignored). Such an algorithm should easily allow a truly cyclic implementation, without using a stack.

  • Yes, thanks for the reply, good optimization. I simply doubted that my arguments about sorting were correct. - Nikolay Petrov

Perhaps here the decision without sorting is meant?

Type, maybe several subarrays, but of different length (an example is not good :) three subarrays of the same length).

subArray [0] {1, 4}; subArray [1] {4, 2}; subArray [2] {2, 3};

  • You just need to find the maximum number of numbers from the array, the sum of which does not exceed K. It does not matter what these numbers are and in what sequence they go. Without sorting, I did not come up with an algorithm whose complexity is less than O (n * log n). But I can not prove the correctness of the solution with sorting. The first thing that comes to mind: If array A is sorted, and we know that the sum of the first i elements does not exceed K, and the sum of the first i + 1 elements is greater than K, then there is no such element among the first i elements that can be replaced more than one element from subarray A [i + 1:], so that the sum was <K — Nikolai Petrov
  • Is there a mistake in my reasoning? - Nikolai Petrov