I have been asked to give a dynamic algorithm that would take a sequence of an even amount of numbers (both positive and negative) and do the following:
Each "turn" two numbers are chosen to be multiplied together. The algorithm can only access either end of the sequence. However, if the first number chosen is the leftmost number, the second number can be either the rightmost number, or the new leftmost number (since the old leftmost number has already been "removed/chosen") and vice-versa. The objective of the program is to find the maximum total sum of the products of the two numbers chosen each round.
Example:
Sequence: { 10, 4, 20, -5, 0, 7 }
Optimal result: 7*10 + 0*-5 + 4*20 = 150
My Progress:
I have been trying to find a dynamic approach without much luck. I've been able to deduce that the program is essentially only allowed to multiply the end numbers by the "adjacent" numbers each time, and that the objective is to multiply the smallest possible numbers by the smallest possible numbers (resulting in either a double negative multiplication - a positive number, or the least-smallest number attainable), and continue to apply this rule each time right to the finish. Contrastingly, this rule would also apply in the opposite direction - multiply the largest possible numbers by the largest possible numbers each time. Maybe the best way is to apply both methods at once? I'm not sure, as I mentioned, I haven't had much luck implementing an algorithm for this problem.
Let's look at both a recursive and a bottom-up tabulated approach. First the recursive:
{10, 4,20,-5, 0, 7}
First call:
f(0,5) = max(f(0,3)+0*7, f(2,5)+10*4, f(1,4)+10*7)
Let's follow one thread:
f(1,4) = max(f(1,2)+(-5)*0, f(3,4)+4*20, f(2,3)+4*0)
f(1,2), f(3,4), and f(2,3) are "base cases" and have a direct solution. The function can now save these in a table indexed by i,j, to be accessed later by other threads of the recursion. For example, f(2,5) = max(f(2,3)+0*7... also needs the value for f(2,3) and can avoid creating another function call if the value is already in the table. As the recursive function calls are returned, the function can save the next values in the table for f(1,4), f(2,5), and f(0,3). Since the array in this example is short, the reduction in function calls is not that significant, but for longer arrays, the number of overlapping function calls (to the same i,j) can be much larger, which is why memoization can prove more efficient.
The tabulated approach is what I tried to unfold in my other answer. Here, instead of a recursion, we rely on (in this case) a similar mathematical formulation to calculate the next values in the table, relying on other values in the table that have already been calculated. The stars under the array are meant to illustrate the order by which we calculate the values (using two nested for loops). You can see that the values needed to calculate the formula for each (i,j)-sized subset are either a base case or exist earlier in the loop order; these are: a subset extended two elements to the left, a subset extended two elements to the right, and a subset extended one element to each side.