# Modified Max Product dynamic solution very inefficient

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

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)$.