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]
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?
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
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
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
Zeros introduce yet another difficulty, altough we can determine for sure that they will always end up grouped to the right:
1 2 3
With or without an isolated negative number that will therefore have no impact in the result anymore:
1 2 3
A definitive algorithm?
It seems that a more efficient algorithm can be found.
To be continued…