假设我们有一个整数数组 A[1..n]（一些正数和一些负数），我们将其 被要求划分成称为段的连续子数组。任意段的值是 该段中元素的乘积。 A 的分区的值是以下值的总和 它的部分。我们想要找到 A 的最大值划分。 我如何编写计算最大值分区的递推公式？并使用 DP 解决它？
我尝试写一个递归公式： F(i)=Max(A[i-1],A[i-1]*F(i-1))
F(i,j) 等于 A(1)..A(i) 被划分为 j 个数组时的最大和。我们希望计算 k = 1,...,n 上 F(n,k) 的最大值。
< I will give the recurrence relation when time permits >
这里有一个示例，说明了实现递归关系所需的计算。它还展示了如何实现动态规划算法。
A = [3, -2, 5, 2, -1, -4, 1]
如果不是因为至少需要三个负值和四个正值来演示负值的存在如何影响计算，我会在示例中使用较小的数组。
F(0,0) = 0
F(0,1) = F(0,0) + A[0] # 0+ 3 = 3
F(1,1) = F(0,0) + A[0]*A[1] # 0- 6 = -6
F(1,2) = F(0,1) + A[1] # 3- 2 = 1
F(2,1) = 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) = F(1,2) + A[2] # 1+ 5 = 6
F(3,1) = 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) = F(2,3) + A[3] # 6+ 2 = 8
F(4,1) = 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) = F(3,4) + A[4] # 8- 1 = 7
F(5,1) = 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) = F(4,5) + A[5] # 7- 4 = 3
F(6,1) = 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) = F(5,6) + A[6] # 3+ 1 = 4
计算最优解的最后一步如下。
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
最优解由
F[6,3] #=> 57573F[6,3]F[6,3]F(5,2) + A[6] # 56+1 = 57*
这告诉我们第三组是：
[A[6]] #=> [1]
然后我们检查
F(5,2)F(5,2)F(4,1) + A[5] # 60-4 = 56*
这告诉我们第二组是：
[A[5]] #=> [-4]
然后我们检查
F(4,1)F(4,1)F(0,0) + A[0]*...*A[4] # 0+60 = 60
这告诉我们第一组是（我们已经知道的）：
[A[0], A[1], A[2], A[3], A[4]] #=> [3, -2, 5, 2, -1]
总而言之，各组如下，计算如下：
[[3, -2, 5, 2, -1], [-4], [1]]
3*(-2)*5*2*(-1 + -4 + 1
60 -4 + 1 = 57