剑指offer 14 求总和一定的某数的因子相乘最大值

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]k[1]...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

这道题的官方解法是, 进行不同的切割方法, 得到的两段i和n-i. 取i(n-i)或者 i[cut(n-i)]的最大值. 因为i是逐渐递增的, 因此cut[n-i]的数组也逐渐补全.

我的方法是: 最大的乘法结果一定是这个是x等分的数相乘. 那么x有多少种取法呢? 考虑到分解成1就毫无意义, 那么x一定小于等于n/2. 那么我们就对这几种等分方法分别求最大值, 然后取最大.

int cuttingRope(int n){
    if(n == 2) return 1;
    if(n == 3) return 2;
    int result = 0;

    //分成i个绝对值<=1的因子
    for(int i = 2; i <= n / 2; i++)
    {
        int *p = (int*) malloc(sizeof(int) * i);
        int j;
        for(j = 0; j < i; j++)
        {
            p[j] = n / i;
        }

        int temp = n%i;
        for(j = i-1;temp>0;temp--,j--)
        {
            p[j] +=1;
        }

        temp = 1;
        for(j = 0; j<i; j++)
        {
            temp *=p[j];
        }

        if(temp > result) result = temp;

        free(p);
    }

    return result;
}