How to maximize the sum of elements selected from a list?

Question

Algorithms

A list of natural positives is given.
From the list, you can select a certain number of elements, so that the difference between the indices of consecutive elements is at least K. It is
necessary to maximize the sum of the selected elements.

For example, given a list:
7, 18, 6, 10, 12, 128
AND K == 3. In this case, the answer will be a set of elements 1.5 whose values ​​are 18 and 128, respectively.

At the same time, the idea that you must first select the maximum element, and then dance from it does not fit.
For example, consider such an array with the same K:
19, 20, 1, 17, 1, 1, 17, 1

If we select element 1(20), then element 6(17) will be the next available element, since element 3 can no longer be chosen, since the difference of indices is less than K (3-1 < K) and the sum of these elements == 37.
But if we choose not the maximum - 0(19), then you can get a combination of 0,3,6 - the difference of the indices is not more than K, and the sum of 53 - any more than 37

What are your ideas? The timing of searching for combinations is important - the lists are long.

Answer 1

In general, an approximate solution plan is as follows:
We start looking at the elements from the end of the list. The last k elements are entered into the cache as is, there is no getting away from them. Next, for each element with number i, you need to look at how it combines with elements i + k .. i + 2k. There is no point in looking further, as this will only worsen the situation. And so we go to the first element. Then we choose the best of the elements with numbers 1 .. k. It seems like the code is linear with respect to the size of the list (no more than k (n + 1) operations).
Implementation code:
https://ideone.com/ZU8Mrr

Answer 2

Is there a limit to the number of elements in a list? If there is, I would do this: I would build all combinations from the allowable number of elements, while calculating their sums. Then I would sort these objects in descending order of the sum, and then, starting from the largest sum, I would check whether the condition is satisfied by K. (this is very simple). As soon as the condition is satisfied - the maximum possible amount is found.
But if suddenly there is no specified restriction, then, alas, we return again to the NP-hard problem.

Answer 3

You need to create an additional list B and fill it in such a way that cell B[I] contains the maximum possible sum of elements A[0..I]
If the list consists of 1 element, then the answer will be the element itself
If 2 elements, then for I=1 it will be max(B[0], A[1])
If there are 3 elements and K = 1, then for I=2 the answer will be max(B[1], A[2] + B[0])

Answer 4

This is a standard dynamic programming problem. For example, enter f(i) - the maximum amount that can be obtained by taking some of the first i elements.
Recalculation: f(i) = max(f(i-1), a[i-1] + f(i-k))- here we either don't take the last element, in which case the answer is f(i-1) or take it - in which case we must skip k-1 of the following elements. Base: f(i<=0) = 0.
You can reduce memory consumption by counting from the bottom up in the array and storing only the last k elements of f[].

Answer 5

For example, given a list:
7, 18, 6, 10, 12, 128
K>=3

1. First, split the stream with the highest frequency (K=>min) into several groups within the same minimum period (K) and look for the largest amount in each such group:
7, 10
18, 12
6, 128 (the largest amount)
2. Then , expand the range in the opposite direction:
18, 128 (the largest amount)
7, 128
3. Repeat everything from the found place again with a minimum K, gradually increasing it to the size of the distance found in the previous step.
And so on until the entire input stream of values ​​\u200b\u200bis finished.