You are given a list, L, with the length N. L contains N random positive integer values. You are only able to select from the outer edges of the list (left/right), and after each selection every value in the remaining list increase by a factor of the current selection. The goal is to maximize the total sum of the selection you make until the list is empty.
An example of L where N = 3, [1,10,2].
Starting list [1,10,2], factor = 1.
- Chosen path left
New list [10 * factor, 2 * factor] => [20, 4], where factor = 2
- Chosen path right
New list [10 * factor] => [30], where factor = 3
Total value = 1 + 4 + 30 => 35.
Output: should be the total sum of all selections, and the list of all the directions taken to get there. 35 (left, right, left). Keep in mind that the the most important part is the total sum. There may exist more than one path that leads to the same total sum, for example 35 (left, right, right).
Test case 1
[3,1,3,1,1,1,1,1,9,9,9,9,2,1] => 527
(right left left left left left left left left right left left left left)
Test case 2
[1,1,4,1,10,3,1,2,10,10,4,10,1,1] => 587
(right left left right left left left left left left right right left right)
Rules
This is code-golf, shortest codes in bytes win.
Standard loopholes are forbidden.
(right, right, ...)
, then the maximum you can get seems to be523
. The reason as to why becomes a bit clearer (to me, at least) when you think of this backwards. Start by multiplying the9
s by large numbers that keep getting smaller. Then you have the option of multiplying a relatively large number by1
on the left, or2
on the right. You probably want to multiply by2
, which is why you don't take it immediately, and why the first moves are(right, left, ...)
. \$\endgroup\$ – zgrep Oct 15 '18 at 7:56