CODEWITHSUNDEEP
algorithmdynamic-programming
user15049375
user15049375

Reputation: 33

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

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.

enter image description here

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

Update Based on @trincot solution, I revamped the soln to not use memoization

Sub problem Defn

Let T(i) store the start offset where inserting the X operator in Z yields max value for i : 1 < i < k.

Pseudo code

`
    T(0) = 0
    for i = 1 -> k:
      max = 0
    for j = T(i-1) + 1 -> n:
          result = Z[1..j] * Z[j+1..n]
          if result > max
           max = result
           T(i) = j
  
     val = 1
    for i = 1 -> k:
          val = val * Z[T(i-1)+1...T(i)]
    val = val * Z[T(k)+1..n]

Upvotes: 1

Views: 526

Answers (3)

trincot
trincot

Reputation: 350770

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);
}

// A few example runs:
console.log(solve('8473817', 1));  // 6922441
console.log(solve('21322', 2));    // 1368
console.log(solve('191111', 2));   // 10101

Bottom up

The same can be done in an iterative algorithm -- bottom-up instead of top-down. Here we can save one dimension of the memoization array, as the same array can be re-used for the next value of k as it increases from 0 to its final value:

function solve(z, k) {
    const memo = Array(z.length);
    // Initialise for k=0:
    //    the best product in a suffix is the suffix itself
    for (let i = 0; i < z.length; i++) {
        memo[i] = +z.slice(i);
    }
    for (let kk = 1; kk <= k; kk++) {
        for (let i = 0; i < z.length - kk; i++) {
            // find best position for multiplication
            let result = 0;
            for (let j = i + 1; j < z.length - kk + 1; j++) {
                result = Math.max(result, +z.slice(i, j) * memo[j]);
            }
            memo[i] = result;
        }
    }
    return memo[0];
}

// A few example runs:
console.log(solve('8473817', 1));  // 6922441
console.log(solve('21322', 2));    // 1368
console.log(solve('191111', 2));   // 10101

Upvotes: 1

rossum
rossum

Reputation: 15693

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.

Upvotes: 0

btilly
btilly

Reputation: 46455

(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.

Upvotes: 0

Related Questions