How to find the maximum sum of elements of a list with a given minimum distance between them

Question

I have been looking for a way to find the possible combinations of a list, given a minimal distance of 3 between all the numbers.

Suppose we have

list = [23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11]

The best possible combination would be 23 + 238 + 238 + 238 = 737.

I've tried parsing the list and selecting each time the max of the split list[i:i+4], like so :

23 -skip three indexes -> max of [238, 11, 12, 23] : 238 -skip three indexes -> max of [48, 10, 55, 238] : 238 skip three indexes -> max of [48, 10, 55, 238] : 238

This worked with this case, but not with other lists where I couldn't compare the skipped indexes.

Any help would be greatly appreciated.

Answer 1

Here is something that works, as far as I can tell.

list = [23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11]

def max_sum(list):
    if len(list) == 0:
        return 0, ""
    elif len(list) <= 4:
        return max(list), " "+str(max(list))
    else:
        best_total = 0
        for i in range(4):
            a = max_sum(list[i+4:])
            if list[i]+a[0] > best_total:
                best_total =  list[i]+a[0]
                terms = str(list[i])+" "+a[1]
        return best_total, terms
        
def format_max_sum(list):
    a = max_sum(list)
    print("The best combination is: " + " + ".join(a[1].split())+ f" = {a[0]} ." )
    
format_max_sum(list)
# The best combination is: 23 + 238 + 238 + 238 = 737 .

Answer for the additional question (I only tested it on the list you provided, but it should work on any list (unless, of course, it doesn't :) ):

list = [23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11]

def max_n_sum(list, n):
    if len(list) < 4*n-3:
        return -1, ""
    elif n == 1:
        return max(list), " "+str(max(list))
    else:
        best_total = 0
        for i in range(len(list)-4*n+4):
            a = max_n_sum(list[i+4:],n-1)
            if list[i]+a[0] > best_total:
                best_total =  list[i]+a[0]
                terms = str(list[i])+" "+a[1]
        return best_total, terms
        
def format_max_n_sum(list,n):
    a = max_n_sum(list,n)
    if a[0] == -1:
        print(f"This list is too short to support {n} values")
    else:
       b = "s" if n>1 else ""
       print(f"The best combination of {n} term" + b + " is: " + " + ".join(a[1].split())+ f" = {a[0]} ." )
    
format_max_n_sum(list, 1)
# The best combination of 1 term is: 238 = 238 .
format_max_n_sum(list, 3)
# The best combination of 3 terms is: 238 + 238 + 238 = 714 .
format_max_n_sum(list, 6)
# This list is too short to support 6 values

Explanation of the calculus:

• To support n values, the list must have at least this size:(o = valid values, xxx = 3 values skipped): o xxx o xxx o xxx o ... xxx o , so 4n - 3 values for n "o"s.
• If the list is long enough, it is shaped like this: OOOOOO xxx o xxx o xxx o ... xxx o , OOOOOO being the valid candidates for the first of the n values; and their number is len(list) - (4n - 4) .

Answer 2

To expand on my comment, here is an approach using the graph algorithms in Scipy. The idea is to compute a shortest path but with the path containing negative weights corresponding to the negated list entries. This creates a longest path with the highest weights.

We start with basic definitions:

import numpy as np
from scipy.sparse import csgraph


lst = [23, 48, 10, 55, 238, 11, 12, 23, 48, 10, 55, 238, 11, 12, 23, 48,
       10, 55, 238, 11]
mindist = 4

List entries are nodes in a directed graph. We add an end note to that. For this graph, we create an adjacency matrix. Scipy's documentation clarifies that these are defines as such:

If there is a connection from node i to node j, then G[i, j] = w.

For the weight w we use the negative of the list entry because algorithms are set up to find shortest routes = lowest values. Also, for the implicit connection from each node to the end of the list, we use the value -1. To make this possible, "-1" becomes our new zero and all values must be lower than that. In other words:

weights = -1 - np.asarray(lst)

Now to the matrix:

nodes = len(lst)
adjacency = np.zeros((nodes + 1, ) * 2, dtype=weights.dtype)

From each node, we can reach the remaining nodes. We only have to consider entries to right of the current entry.

for idx in range(nodes - 1):
    remain = idx + mindist
    adjacency[idx, remain:-1] = weights[remain:]

At any point we can stop adding more entries to our path, read: We can directly go to the end node.

adjacency[:-1, -1] = -1

Side note: If our input list is non-negative, adding more entries never hurts. In that case we could remove connections to the end node for inner nodes that can still reach more inner nodes. May save some time.

Now let's compute the actual shortest path from the start node index 0.

dists, pred = csgraph.shortest_path(
    adjacency, return_predecessors=True, indices=0)

Finally, we wander the list of predecessors from end to start.

cur = pred[-1]
indices = [cur]
while cur:
    cur = pred[cur]
    indices.append(cur)
indices.reverse()

Let's look at the results:

print(indices)
print([lst[idx] for idx in indices])

[0, 4, 11, 18]
[23, 238, 238, 238]

Overall I'm not sure this is algorithmically superior to a simple brute-force approach. But it's certainly nice and fancy-looking ;-)