Maximum-value partition using Dynamic programming

Question

Suppose we are given an array A[1..n] of integers (some positive and some negative) which we are asked to partition into contiguous subarrays called segments. The value of any segment is the product of the elements in that segment. The value of a partition of A is the sum of the values of its segments. We want to find the maximum-value partition of A. How I can write the recurrence formulation for computing the maximum-value partition.?and solve it using DP?

I tried to wrote a recurrence formulation which is : F(i)=Max(A[i-1],A[i-1]*F(i-1))

Answer 1

F(i,j) equals the maximum sum of products when [A(0), A(1),...,A(i)] has been partitioned into j arrays. We wish to compute the maximum of F(n-1,k) over k = 1,...,n, where n is the size of the array.

Define F(0,0) = 0. The recurrence relation is as follows, for i = 1,...,n-1 and j = 1,...,i+1. Maxima are taken over values of the index k.

F(i,j) = max_{max(j-2,0)≤k≤i-1}F(k,j-1)+∏_k+1≤h≤ia_h

Some readers may be curious as to why the range over which k is taken is max(j-2,0)≤k≤i-1 and not 0≤k≤i-1. Consider, for example, the calculation of F(5,4) if k ranged from 0 to i-1 (4):

F(5,4) = max [F(0,3) + A[1]*...*A[5], F(1,3) + A[2]*...*A[5],
              F(2,3) + A[3]*...*A[5], F(3,3) + A[4]*A[5], F(4,3) + A[5]]

However, F(0,3) equals the maximum sum when [A(0)] has been partitioned into 3 arrays, which is not possible. Nor is F(1,3), which equals the maximum sum when [A(0), A(1)] has been partitioned into 3 arrays. This calculation is therefore as specified by the recurrence relation:

F(5,4) = max_2≤k≤4F(k,j-1)+∏_k+1≤h≤5a_h

Example calculation

The following example illustrates the calculations required to implement the recurrence relation. It also shows how a dynamic programming formulation would be implemented.

A = [3, -2, 5, 2, -1, -4, 1]

I would have used a smaller array for the example were it not for that fact that at least three negative and four positive values were needed to to demonstrate how the presence of negative values affect the calculations.

F(0,0) = 0

---

F(0,1) = F(0,0) + A[0]                #   0+  3 =    3

---

F(1,1) = max [F(0,0) + A[0]*A[1]]     #   0-  6 =   -6*
F(1,2) = max [F(0,1) + A[1]]          #   3-  2 =    1*

---

F(2,1) = max [F(0,0) + A[0]*A[1]*A[2]]#   0- 30 =  -30*
F(2,2) = max [F(0,1) + A[1]*A[2],     #   3- 10 =   -7
              F(1,1) + A[2]],         #  -6+  5 =   -1*
F(2,3) = max [F(1,2) + A[2]]          #   1+  5 =    6*

---

F(3,1) = max [F(0,0) + A[0]*...*A[3]] #   0- 60 =  -60*
F(3,2) = max [F(0,1) + A[1]*...*A[3], #   3- 20 =  -17
              F(1,1) + A[2]*A[3],     #  -6+ 10 =    4*
              F(2,1) + A[3]]          # -30+  2 =  -28
F(3,3) = max [F(1,2) + A[2]*A[3] ,    #   1+ 10 =   11*
              F(2,2) + A[3]]          #  -1+  2 =    1
F(3,4) = max [F(2,3) + A[3]]          #   6+  2 =    8*

---

F(4,1) = max [F(0,0) + A[0]*...*A[4]] #   0+ 60 =   60*
F(4,2) = max [F(0,1) + A[1]*...*A[4], #   3+ 20 =   23*
              F(1,1) + A[2]*...*A[4], #  -6- 10 =  -16
              F(2,1) + A[3]*A[4]],    # -30-  2 =  -32
              F(3,1) + A[4]]          # -60-  1 =  -61
F(4,3) = max [F(1,2) + A[2]*...*A[4], #   1- 10 =   -9
              F(2,2) + A[3]*A[4]],    #  -1-  2 =   -3
              F(3,2) + A[4]]          #   4-  1 =    3*
F(4,4) = max [F(2,3) + A[3]*A[4],     #   6-  2 =    4
              F(3,3) + A[4]]          #  11-  1 =   10*
F(4,5) = max [F(3,4) + A[4]]          #   8-  1 =    7*

---

F(5,1) = max [F(0,0) + A[0]*...*A[5]] #   0-240 = -240*
F(5,2) = max [F(0,1) + A[1]*...*A[5], #   3-240 = -237
              F(1,1) + A[2]*...*A[5], #  -6+ 40 =   34
              F(2,1) + A[3]*...*A[5], # -30+  8 =  -22
              F(3,1) + A[4]*A[5],     # -60+  4 =  -56
              F(4,1) + A[5]]          #  60-  4 =   56*
F(5,3) = max [F(1,2) + A[2]*...*A[5], #   1+ 40 =   41*
              F(2,2) + A[3]*...*A[5], #  -1+  8 =    7
              F(3,2) + A[4]*A[5],     #   4+  4 =    8
              F(4,2) + A[5]]          #  23-  4 =   19
F(5,4) = max [F(2,3) + A[3]*...*A[5], #   6+  8 =   14
              F(3,3) + A[4]*A[5],     #  11+  4 =   15*
              F(4,3) + A[5]]          #   3-  4 =   -1
F(5,5) = max [F(3,4) + A[4]*A[5],     #   8+  4 =   12*
              F(4,4) + A[5]]          #  10-  4 =    6
F(5,6) = max [F(4,5) + A[5]]          #   7-  4 =    3*

---

F(6,1) = max [F(0,0) + A[0]*...*A[6]] #   0-240 = -240* 
F(6,2) = max [F(0,1) + A[1]*...*A[6], #   3- 80 =  -77
              F(1,1) + A[2]*...*A[6], #  -6+ 40 =   34
              F(2,1) + A[3]*...*A[6], # -30+  8 =  -22
              F(3,1) + A[4]*...*A[6], # -60+  4 =  -56
              F(4,1) + A[5]*A[6],     #  60-  4 =   56*
              F(5,1) + A[6],          #-240+  1 = -239
F(6,3) = max [F(1,2) + A[2]*...*A[6], #   1+ 40 =   41
              F(2,2) + A[3]*...*A[6], #  -1+  8 =    7
              F(3,2) + A[4]*...*A[6], #   4+  4 =    8
              F(4,2) + A[5]*A[6],     #  23-  4 =   19
              F(5,2) + A[6]]          #  56+  1 =   57*
F(6,4) = max [F(2,3) + A[3]*...*A[6], #   6+  8 =   14
              F(3,3) + A[4]*...*A[6], #  11+  4 =   15
              F(4,3) + A[5]*A[6],     #   3-  4 =   -1
              F(5,3) + A[6]]          #  41+  1 =   42*
F(6,5) = max [F(3,4) + A[4]*...*A[6], #   8+  4 =   12
              F(4,4) + A[5]*A[6],     #  10-  4 =    6
              F(5,4) + A[6]]          #  15+  1 =   16* 
F(6,6) = max [F(4,5) + A[5]*A[6],     #   7-  4 =    3
              F(5,5) + A[6]]          #  12+  1 =   13* 
F(6,7) = max [F(5,6) + A[6]]          #   3+  1 =    4*

Note some some of these calculations compute a maximum over the elements of an array containing a single element. For example, I could have written

F(6,1) = F(0,0) + A[0]*...*A[6]       #   0-240 = -240* 

but the way it is written is probably closer to how it would be implemented in code.

---

The last step in calculating an optimal solution is as follows.

  max [F[6,1], F[6,2], F[6,3], F[6,4], F[6,5], F[6,6], F[6,7]] 
= max [ -240 ,    56 ,    57 ,    42 ,    16 ,    13 ,     4 ]
= 57

The optimal solution is given by F[6,3] #=> 57 as 57 is the largest value. That tells us that the optimal solution has 3 groups (the second index of F[6,3]) and has an optimal value of 57. The optimum for F[6,3] is given by the line (with the asterisk):

F(5,2) + A[6] #  56+1 = 57*

This tells us that the third groups is:

[A[6]] #=> [1] 

We then examine F(5,2). The optimum for F(5,2) is given by line:

F(4,1) + A[5] #  60-4 = 56*

This tells us that the second groups is:

[A[5]] #=> [-4]

We then examine F(4,1). The optimum for F(4,1) is given by the line:

F(0,0) + A[0]*...*A[4] #  0+60 = 60

This tells us that the first groups is (what we already knew):

[A[0], A[1], A[2], A[3], A[4]] #=> [3, -2, 5, 2, -1]

We then examine F(0,0) which tells us we are finished.

In summary, the groups are as follows, with the calculations given below:

[[3, -2, 5, 2, -1], [-4], [1]]
  3*(-2)*5*2*(-1  +  -4  + 1
         60          -4  + 1 = 57