今日头条面试算法题

总和不变，积最大。那么就是要分成两段。每段的和尽量靠近总和的一半。 这就成了背包问题。请搜下背包问题。

这个题暴力复杂度也不高啊，O(N)，为啥不考虑暴力呢

其实就是不等式定理，x+y=k，(x-y)2>=0,则可以推出xy<=k2/4，则x*y的最大值是k2/4,也就是x=y=k/2时最大。

可转化为容量为sum/2的01背包问题, i初始值为最后一个元素下标,j初值为sum/2,意思为用下标<=i的元素凑出最接近j的值 pack(i,j)=max(pack(i-1,j),pack(i-1,j-num[i])+num[i])) 问题:没考虑负数,而且长度偶数这个条件没用上,估计不是最优解

result = x(sum-x)，最接近sum/2的应该是最优的，因此转化为dp求解，如果sum不是很大的话。。。。

亲，拿到头条的offer了吗？

不能简单的用背包问题去套，因为背包问题中物品的重量是不能超过上限的，而这道题目两个背包中一个超过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的大四狗