1
$\begingroup$

The modified max product problem is as follows: given integer string $z_1\ldots z_n$, and an integer $k \leq n - 1$, what is the maximum product that can be formed by placing $k$ multiply signs in between the numbers, in the best possible configuration.

This has ${n-1 \choose k-1} = \frac{n!}{(n-k)!k!}$ configurations...so if $k$ is somewhere around $n/2$, then it should be a very large search space...so maybe some complexity makes sense. However, I think I screwed up (aside from any indexing errors).

I have an $O(n^5)$ algorithm...

maxprod(z,n,k):
    for i = 1 to n:
        for j = 1 to n:
            T(i,j,0) = Z[i ... j] as an integer

    for s = 2 to n:
        for i = 1 to n - s:
            let j = i + s-1

            for a = max(0,k-n-s-1) to s-1: (all sizes of a)

                T(i,j,a) = max(...

                    for v = i to j: (splitting i and j)
                        for b = max(0,a-(j-v-1)) to min (a-1,v-1):
                            T(i,v,b)*T(v+1,j,a-1-b)
                  )
    Return T(1,n,k)

And I created it using a recursion,

$ T(i,j,a) = \mathop{max}\{T(i,v,b)\times T(v+1,j,a-1-b)\} $

Where $v$ is varied from $i$ to $j$ and $b$ is varied from the minimum value it needs to be to the max it can be (for the multiplies needed in the substring such that exactly $k$ multiplies are used).

Is this even properly implemented? Is there a faster solution? Where am I going wrong? For some reason, I am struggling with dynamic programming...(only three or four dp problems solved so far though).

But then, I am thinking: I only do a max across two dimensions, inside the three for loops necessary to fill out a 3d array. This is essentially the fastest I can possibly do it in terms of $O(.)$ with my recursion. Where am I screwing up, conceptually? This problem can't be as difficult as I made it...

$\endgroup$
1
$\begingroup$

Why do you split it in the middle? Multiplication is associative so you don't have to do that. Considering only the last multiply sign would be fine. Here's a simpler recursion: $T(1,j,a)=\max\{T(1,v,a-1)\times T(v+1,j,0)\}$. I use the same symbols as yours so you can see the difference. The first dimension is useless so the table is actually an $n \times k$ array. Each function call takes $O(n)$, so the complexity is $O(n^2k)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.