Optimizing edge selection from a list of numbers

Question

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.

1. Chosen path left

New list [10 * factor, 2 * factor] => [20, 4], where factor = 2

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.

Answer 1

k, 48 bytes

{{x@*&*+x=*|/x}@{(+/x*1+<y*|!#x;y)}[x]'+!(#x)#2}

Try it online! It simply tries all possibilities, and chooses the first one with the maximum value. Left/right encoded as 0/1.

{                                              } /function accepts x
                                       +!(#x)#2  /all possible selections
                { +/x*1+<y*|!#x   }[x]           /calculate the total sum
                 (             ;y)               /also record the selection with each sum
                                      '          /map over all selections
 {x@*&*+x=*|/x}@                                 /choose the one with max total sum

This can probably be golfed further.

Answer 2

Haskell, 91 90 89 bytes

Encoding the left/right decision as 0/1:

(1%)
f%l@(h:t)|x<-f+1,(a,b)<-x%t,(c,d)<-x%init l=max(a+f*h,0:b)(c+f*last l,1:d)
_%l=(0,l)

Try it online!

Answer 3

Ruby, 120 bytes

->l{[*(w=[0,1]).product(*[w]*~-s=l.size).map{|x|a,b=l.clone,0;[x,x.sum{|c|(b+=1)*(c>0?a.pop: a.shift)}]}].max_by &:last}

Try it online!