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.

• feddy: I will update the question to make it more clear. The values of the remaining list increase by a factor of the current selection. In the first list [1,10,2] the factor is 1 since it is the first selection. Then the list becomes [10 * factor, 2 * factor], the factor is 2 since it is the second selection. The last list is [10 * factor], which is 3 since it is the third selection. I hope that makes it more clear.
• feddy: Both, I will update the question.
• Wheat Wizard: You've tagged this with code-golf, could you make it explicit what is required to be valid and how answers are scored in the question? Also btw, if you visit our meta we have a sandbox where you can get feedback before posting.
• feddy: @JonathanAllan fixed!
• zgrep: @KevinCruijssen As best as I can tell, you understand the algorithm correctly. And yet, if you start with (right, right, ...), then the maximum you can get seems to be 523. The reason as to why becomes a bit clearer (to me, at least) when you think of this backwards. Start by multiplying the 9s by large numbers that keep getting smaller. Then you have the option of multiplying a relatively large number by 1 on the left, or 2 on the right. You probably want to multiply by 2, which is why you don't take it immediately, and why the first moves are (right, left, ...).

Answer 1

k, (削除) 48 (削除ここまで) (削除) 43 (削除ここまで) 38 bytes

-5 bytes thanks to ngn.

{a@*>*+a:x{(+/x*1+<y*|!#x;y)}/:+!2|-x}

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

{ } /functions accepts x
 +!2|-x /all possible selections
 { +/x*1+<y*|!#x } /calculate the total sum
 ( ;y) /also record the selection with each sum
 x /: /map over all selections
 a@*>*+a: /choose the one with max total sum

This can probably be golfed further.

• ngn: golfed a little further: {a@*&*+a=*|/a:x{(+/x*1+<y*|!#x;y)}/:+!2|-x}

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!