Creasing for Loot

Question

Introduction

After a long battle, you have managed to defeat a Sphinx in a contest of riddles. The Sphinx, impressed with your skill, wishes to give you a reward commensurate with your cleverness, and conjures into existence a strip of magical parchment divided into eight boxes, each containing a numeral.

"Crease the parchment," says the Sphinx, "such that the boxes overlap, and those boxes will merge either through addition or multiplication. When one box remains, its value will be your reward in gold coins."

Task

You must write a program or function which takes as input a list/array/whatever of eight natural numbers, and returns/prints the maximum possible reward obtainable through a series of 'crease' operations.

Mechanics

The 'crease' operation is performed on some number of cells, and with either + or * as the operator. The first n cells of the list are folded across and merged with their destination cells using the operator. Any cells which are not consumed in the merge operation are left unmodified.

Here is an example of creasing using n=3 cells:

using either addition, which would result in this:

or multiplication, which would result in this:

Note: For simplicity, creasing with fewer than 1 cell is disallowed, as is creasing with a number of cells greater than or equal to the length of the list. However, a list can by creased by more than half its cell count.

A list of 8 cells can be creased by 5, resulting in a new list of length 5: [0,1,2,3,4,5,6,7] creased by 5 cells using the + operator would give [9,9,9,1,0].

Scoring

Standard code golf rules - the code which produces correct output and has the fewest number of bytes wins.

Bonus: If your code also returns/prints the sequence of crease operations which leads to the maximal reward, multiply your score by 0.8. Example output might look like:

crease 5 +
crease 2 *
crease 2 +
crease 1 *

Examples

Test your code using these inputs and results, in the form of input - maximum reward:

[0, 1, 2, 3, 4, 5, 6, 7] - 7560
[0, 9, 0, 3, 2, 6, 1, 5] - 1944
[0, 1, 0, 3, 0, 2, 0, 4] - 36
[6, 0, 9, 1, 9, 0, 7, 3] - 11907
[0, 5, 2, 0, 1, 3, 8, 8] - 2560

Answer 1

Pyth, 31 bytes

Le+bSyMsm,sMJ.T,_<bd>bdm*FkJtUb

This defines a function, y, which computes the crease value.

Demonstration.

This uses the recusive method, taking the maximum of the score of every possible successor.

The base case of the recursion is implemented by concatenating the input to the sorted values of the possible successors, and then taking the end of the resultant list. If there is only 1 element in the input, there are no successors, and therefore the end of the list is the one element in the input.

Answer 2

C#, 275 272 bytes

It's simply a recursive function that traverses every branch and returns the best score.

Indented for clarity:

using M=System.Math;
int F(int[]n){
    int b=0,g,h,i=0,j,k,l=n.Length;
    if(l<2)
        return n[0];
    for(;++i<l;){
        int[]m=new int[k=M.Max(i,l-i)],o=new int[k];
        for(j=0;j<k;j++){
            m[j]=((g=i-j-1)<0?0:n[g])+((h=i+j)<l?n[h]:0);
            o[j]=h<l&g>=0?n[g]*n[h]:m[j];
        }
        b=M.Max(b,M.Max(F(m),F(o)));
    }
    return b;
}