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] => , 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)
This is code-golf, shortest codes in bytes win.
Standard loopholes are forbidden.