You have a list of N real numbers, x1 to xN. You decide you want to sum the products of the i first terms, for i from 1 to n. Let’s call this operation multadd.

A simple example with the following list L = [1, 5, 3]

1

multadd(L) = 1 + 1 * 5 + 1 * 5 * 3 = 21

One thing we can notice right away: the result depends on how we order the numbers in the list.

How to order the numbers in the list so that the result is maximized?

Hard solution

If all numbers are positive, the answer is simply to order them in descending order. But remember that any number can be negative, or 0.

The naive algorithm will check every possible permutation, and display the maximum result and one way to accomplish it. Here’s a working example in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import itertools
from operator import mul

def multadd(L):
  """Sum of the multiplied i first elements, for i from 1 to N"""
  return sum([reduce(mul,L[:i]) for i in range(1,len(L)+1)])

def multaddmax(L):
  """Find the maximizing order"""
  tempmax = float("-inf")
  for p in itertools.permutations(L):
    temp = multadd(p)
    if temp > tempmax:
      tempmax = temp
      result = p
  return tempmax, result

The complexity is too high for this function to be applied to lists with lengths over ten elements, but at least we’re sure we have the right answer.

Now it’s easy to realize the problem is potentially a lot weirder and more complicated that we initially thought, with the addition of negative numbers:

1
2
3

print multaddmax([-5, -4, -3, -2, -1, -10, -10, -0.9, -0.3, -0.1])

(11320.0, (-4, -5, -3, -10, -2, -10, -0.3, -1, -0.1, -0.9))

Difficult to see a simple pattern that would help us towards a more efficient solution. Although we can notice a few interesting occurrences: negative numbers usually end up being “paired” together, higher value first, and ordered such that they go further and further from the median value.

1
2
3

print multaddmax([-8, -7, -6, -5, -4, -3, -2, -1])

(39916, (-4, -5, -3, -6, -2, -8, -1, -7))

Zeros introduce yet another difficulty, altough we can determine for sure that they will always end up grouped to the right:

1
2
3

print multaddmax([-4, -3, -2, -1, 0, 0, 2, 4, 6])

(1894, (-2, -4, -1, -3, 6, 4, 2, 0, 0))

With or without an isolated negative number that will therefore have no impact in the result anymore:

1
2
3

print multaddmax([-4, -3, -2, 1, 0, 0, 2, 4, 6])

(1521, (-3, -4, 6, 4, 2, 1, 0, -2, 0))

A definitive algorithm?

It seems that a more efficient algorithm can be found.

To be continued…