Max Product of a string that requires K multiplication operators to be inserted-CodePudding

Maximum Product.

The input to the problem is a string Z = z1,z2.....zn where each zi is any number between 1...9 and an integer k where 0 <= k < n.

An example string is Z = 8473817, which is of length n = 7. We want to insert k multiplication operators X into the string so that the mathematical result of the expression is the largest possible. There are n - 1 possible locations for the operators, namely, after the ith character where i = 1,....., n - 1.

For example, for input Z = 21322 and k = 2, then one possible way to insert the X operators is: 2 X 1 X 322 = 644, another possibility is 21 X 3 X 22 = 1386.

Design a dynamic programming to output the maximum product obtainable from inserting exactly k multiplication operators X into the string. You can assume that all the multiplication operations in your algorithm take O(1) time.

I am approaching this using the Matrix Chain Multiplication method where you compute smaller subproblem along the upper diagonal. This works when K=1 i.e. one multiplication operator is inserted. In the picture below, I have used 8473817 as an example and shown that 8473 X 817 yields the highest product. How do I scale this solution for K > 1 and K < N.

Update: adding a pseudo code.

let A(i,j) store the max product for the strings A(i...j) 1 < i < j < n

for i = 1 -> n:
   A(i,i) = Z(i) 

for s = 1 -> n-1:
    for i = 1 -> n-s:
        j = i   s
        A(i,j) = 0
        for l = i -> j-1:
          A(i,j) = max (A(i,j), A(i,l) * A(l 1,j)
return A(1,n)

The above code works when k = 1. How do I scale this up when k > 1 and less than n

CodePudding user response：

(Code not supplied because this is homework.)

You have found that you can use the method once and get a solution for k=1.

Can you do it and find the best solution ending at every position in the string?

Now can you use the output of that second generalization and a similar method to get a complete solution for k=2?

Now can you write this a loop to solve for arbitrary k?

If you can do all that, then finishing is easy.

CodePudding user response：

You have n-1 positions and k operators to insert. To me that looks like a binary number with n-1 bits including k 1's and the other positions set to 0.

Systematically generate all permutations of [0..01..1], insert multiplication operators at the 1 positions and calculate the result for each permutation.

CodePudding user response：

Your pseudo code is a dynamic programming solution where you use memoization for every possible slice of z (2 dimensions, starting and ending offset). However, you would only need to memoize the best result for any suffix of z, so you would only need one (starting) offset. A second dimension in your memoization would then be used for the value of k (the number of remaining multiplications).

So you would still need a 2-dimensional table for memoization, but one index would be for k and the other for an offset in z.

Here is an implementation in JavaScript:

function solve(z, k) {
    // Initialise a kxl array (where l is the length of z), filled with zeroes.
    const memo = Array.from({length: k   1}, () => Array(z.length   1).fill(0));
    
    function recur(z, k) {
        if (k == 0) return z;
        let result = memo[k][z.length];
        if (result == 0) {
            for (let i = 1; i <= z.length - k; i  ) {
                result = Math.max(result,  z.slice(0, i) * recur(z.slice(i), k - 1));
            }
            memo[k][z.length] = result;
        }
        return result;       
    }
    return recur(z, k);
}

// Two example runs:
console.log(solve('8473817', 1));  // 6922441
console.log(solve('21322', 2));  // 1368