Dynamic algorithm to find maximum sum of products of "accessible" numbers in an array

Question

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.

Answer 1

You're probably looking for a dynamic programming algorithm. Let A be the array of numbers, the recurrence for this problem will be

f(start,stop) = max( // last two numbers multiplied + the rest of sequence,
                     // first two numbers multiplied + the rest of sequence,
                     // first number*last number + rest of sequence  )

f(start,stop) then is the optimal result for the subsequence of the array beginning at start,stop. You should compute f(start,stop) for all valid values using dynamic programming or memoization.

Hint: The first part // last two numbers multiplied + the rest of sequence looks like:

 f(start,stop-2) + A[stop-1]*A[stop-2]

Answer 2

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.

Answer 3

Let i and j represent the first and last indexes of the array, A, after the previous turn. Clearly, they must represent some even-sized contiguous subset of A. Then a general case for dp[i][j] ought to be max(left, right, both) where left = A[i-2]*A[i-1] + dp[i-2][j], right = A[j+1]*A[j+2] + dp[i][j+2], and both = A[i-1]*A[j+1] + dp[i-1][j+1]; and the solution is max(A[i]*A[i+1] + dp[i][i+1]) for all i except the last.

Fortunately, we can compute the dp in a decreasing order, such that the needed values, always representing larger surrounding subsets, are already calculated (stars represent the computed subset):

{10, 4,20,-5, 0, 7}
  *  *  *  *  *  *
  *  *  *  *
  *  *
     *  *  *  *    (70)
     *  *
        *  *  *  *
        *  *
           *  *    left = (80 + 70)
              *  *

Answer 4

Below is the code snippet of recursive approach.

  public class TestClass {

  public static void main(String[] args) {
    int[] arr = {10, 4, 20, -5, 0, 7};
    System.out.println(findMaximumSum(arr, 0, arr.length - 1));
  }

  private static int findMaximumSum(int[] arr, int start, int end) {
    if (end - start == 1)
        return arr[start] * arr[end];

    return findMaximum(
        findMaximumSum(arr, start + 2, end) + (arr[start] * arr[start + 1]), 
        findMaximumSum(arr, start + 1, end - 1) + (arr[start] * arr[end]),
        findMaximumSum(arr, start, end - 2)+ (arr[end] * arr[end - 1])
        );
  }

  private static int findMaximum(int x, int y, int z) {
    return Math.max(Math.max(x, y), z);
  }
}

The result is 10*4 + 20*7 + -5*0 = 180

and similarly for the input {3,9,7,1,8,2} the answer is 3*2 + 9*8 + 7*1 = 85

Answer 5

Let's turn this into a sweet dynamic programming formula.

We define the subproblem as follows:

• We would like to maximize the total sum, while picking either the first two, the first and last, or the last two values of the subarray i, j.

Then the recurrence equation looks like this:

set OPT(i,j) =
    if i == j
        v[i]
    else if i < j:
        max (
            v[i] + v[i+1] + OPT(i + 2,j),
            v[i] + v[j]   + OPT(i + 1,j + 1),
            v[j] + v[j-1] + OPT(i, j - 2)
        )
    else:
        0

The topological order: either or both i and j are getting smaller.

Now the base case comes when i is equal to j, the value is returned.

And to come to the original problem, calling OPT(0,n-1) returns the maximum sum.

The time complexity is O(n^2). Since we use dynamic programming, it enables us to cache all values. Per subproblem call, we use at most O(n) time, and we do this O(n) times.