If we have a list of integers we can "squish" one of them by:
- decrementing it
- replacing adjacent values with its new value
For example in this list:
If we squish the
8 we get:
The question is:
Given a starting array, what is the largest we can make its sum by repeatedly squishing values?
For example if we are given:
Here the starting sum is
18 but if we squish the
5 or the
9 it will go up. Squishing anything else will make it go down so we will squish them.
Now the sum is
36, but it can still go up, if we squish the left-most
8 it will increase to
We can squish the left-most
7 but it won't change the sum. If we go back and try some other things we will find that the best sum possible is in fact
So the answer here is
Given a list of two or more positive integers as input give the maximum sum that can be attained by repeated squishing.
This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
[2,2,2] -> 6 [4,5] -> 9 [4,6] -> 10 [4,4,6] -> 14 [4,6,5] -> 15 [1,1,9] -> 21 [1,1,1,9] -> 25 [1,8,1,9,1] -> 38 [1,10] -> 18 [1,5,1,1,9,1] -> 37 [9,1,1,1] -> 25 [3,6,7,8,1] -> 31