不能简单的用背包问题去套，因为背包问题中物品的重量是不能超过上限的，而这道题目两个背包中一个超过sum/2，一个不能超过上限sum/2，背包重量加和为sum。

所以得重新构建DP方程。当然这个方程也算是背包的思想

平均分成两个部分，把这个两个部分称为A和B

f[i][j][0] 表示到第i个数时，A 部分的个数有j个，B部分的个数有i-j，此时两部分的和的乘积最大值。

f[i][j][1] 表示取到f[i][j][0]时，A部分的加和。

f[i][j][2] 表示取到f[i][j][0]时，B部分的加和。

sum[i] 表示1~第i个数时的总和

初始值 sum[0] = 0; f[0][0] = 0; 

sum[i]=sum[i-1]+a[i];

if (f[i-1][j-1][1]*f[i-1][j-1][2] //如果第i个选A部分 

    >

     f[i-1][j][1]*f[i-1][j][2])   //如果第i个选B部分

 then

     f[i][j][1] = f[i-1][j-1][1]+a[i]; // 选择A部分

     f[i][j][2] = sum[i] - f[i][j][1];

     f[i][j][0] = f[i][j][1]*f[i][j][2];

else

    f[i][j][1] = f[i-1][j][1]+a[i];    //选择B部分

     f[i][j][2] = sum[i] - f[i][j][1];

     f[i][j][0] = f[i][j][1]*f[i][j][2];

最终答案就是f[n][n/2][0]。

处女答，初步考虑，如有不对，请多指教。 

                                                                                                   from 一个手里没有offer的大四狗