基于动态规划的数组最大值划分：递推公式与DP求解问询

问题回顾 #

给定包含正负数的整数数组A[1..n]，将其划分为若干连续子数组（分段），每个分段的值为该段元素的乘积，划分的总取值为所有分段值的和。我们需要找出这个总取值的最大值。

你原递推公式的问题 #

你写的F(i)=Max(A[i-1],A[i-1]*F(i-1))只考虑了两种情况：要么把当前元素单独作为分段，要么把当前元素和前一个结果合并成一个分段。但这个逻辑忽略了负数的特殊情况——如果当前元素是负数，前面的最小乘积（可能是负数）乘以当前负数会得到一个较大的正数，这时候结果会比单独取当前元素或者和前面的最大乘积合并更大。

正确的递推公式（动态规划） #

我们需要同时维护两个动态规划数组，分别记录以当前元素结尾的最大分段乘积和与最小分段乘积和：

• dp_max[i]：表示以数组第i个元素（A[i]）结尾的最大分段乘积和
• dp_min[i]：表示以数组第i个元素（A[i]）结尾的最小分段乘积和

对于每个i（从1到n），我们有三种可能的选择：

1. 单独将A[i]作为一个分段，取值为A[i]
2. 将A[i]加入前一个分段的最大乘积组合，取值为dp_max[i-1] * A[i]
3. 将A[i]加入前一个分段的最小乘积组合（负负得正可能得到更大值），取值为dp_min[i-1] * A[i]

基于这三种情况，递推公式为：

dp_max[i] = max(A[i], dp_max[i-1] * A[i], dp_min[i-1] * A[i])
dp_min[i] = min(A[i], dp_max[i-1] * A[i], dp_min[i-1] * A[i])

最终的最大划分值是dp_max数组中的最大值，因为最优划分可能结束在数组的任意位置。

求解步骤 #

1. 初始化：如果数组为空，返回0；否则dp_max[0] = dp_min[0] = A[0]（这里用0-based索引，对应原数组A[1..n]的第一个元素）
2. 遍历计算：从数组第二个元素开始，依次计算每个位置的dp_max和dp_min
3. 获取结果：遍历dp_max数组，取其中的最大值即为答案

示例验证 #

比如数组A = [2, -3, -2, 4]：

• i=0（A[0]=2）：dp_max[0]=2，dp_min[0]=2
• i=1（A[1]=-3）：三种取值为-3、2*(-3)=-6、2*(-3)=-6 → dp_max[1]=-3，dp_min[1]=-6
• i=2（A[2]=-2）：三种取值为-2、(-3)(-2)=6、(-6)(-2)=12 → dp_max[2]=12，dp_min[2]=-2
• i=3（A[3]=4）：三种取值为4、12*4=48、(-2)*4=-8 → dp_max[3]=48，dp_min[3]=-8

dp_max数组为[2, -3, 12, 48]，最大值是48，对应划分可以是将整个数组作为一个分段（乘积为2*(-3)*(-2)*4=48），这就是最优结果。

内容的提问来源于stack exchange，提问作者albusaidi