当前位置:   article > 正文

每日一题(力扣算法)整数拆分_给定一个正整数 n,将其拆分为两个正整数的和,并使拆分后的整数的乘积最大化。 返

给定一个正整数 n,将其拆分为两个正整数的和,并使拆分后的整数的乘积最大化。 返

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
  • 1
  • 2
  • 3

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
  • 1
  • 2
  • 3

说明: 你可以假设 n 不小于 2 且不大于 58。

第一种方法:
动态规划
对于正整数N(N>=2),最少有两个正整数组成,令k是拆分的第一个正整数,n-k就是剩余的数,n-k可以不进行拆分,也可以进行拆分。因为每个正整数对应的最大乘积取决于比他小的数的乘积,因此可以用动态规划来进行。

首先我们创建一个数组a[n],对于每个数组的元素都存入对应下标的最大乘积值,对于0和1,我们就不进行存入。因此a[0]和a[1]就是0.

当i≥2的时候,假设对i进行拆分的第一个数就是j(1≤j<i),则有以下两种方案:

1.将i拆分成j和i-j的和,且i-j不拆分成更多的正整数 ,此时的乘积是j*(i-j)。
2.将i拆分成j和i-j的和,且i-j拆分成更多的正整数,此时的乘积就是ja[i-j]。
因此,当j固定的时候,
a[j]=max(j
(i-j),j*a[i-j]).j的范围是1~i-1.
由此遍历即可。

int integerBreak(int n) {
    int dp[n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 2; i <= n; i++) {
        int curMax = 0;
        for (int j = 1; j < i; j++) {
            curMax = fmax(curMax, fmax(j * (i - j), j * dp[i - j]));
        }
        dp[i] = curMax;
    }
    return dp[n];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

复杂度分析
时间复杂度:由于进行了两层循环,所以时间复杂度应该是O(n^2).
空间复杂度:只需要数组的开辟,所以空间复杂度是O(n).

另一种方法就是数学的计算:
利用函数极限值来:
将一个给定的正整数拆分成某个特定的正整数,则这些正整数的乘积最大。
定义函数 f(x)表示将给定的正整数 n 拆分成尽可能多的正数 x 的情况下的最大乘积,则可以将n分成n/x项

因此f(x)=x^(n/x) =e^(nInx/x)。
令g(t)= e^t ,h(x)=Inx/x,则有f(x)=g(n*f(x)),由于g(x)是单调递增的,所以f(x)也是单调递增的,(n>0).
计算h(x)的驻点,h’(x)=(1-Inx)/x^2=0,得到驻点x=e.

在0<x<e的时候h’(x)>0,当x>e的时候h’(x)<0,因此x=e的时候是极大值。因此x=e的时候f(x)有最大值,f(x)max=f(e)=e^(n/e).
由于 e 不是整数,因此使用与 e 最接近的整数作为x 的值,x 可以是 2 或 3,此时需要比较 f(2) 与 f(3) 的大小,可以通过计算f(3)/f(2)的值
进行比较。
f(3)/f(2)的最终结果是e^(n/6*(In9-In8)),所以f(3)>f(2).
因此我们应该将给定的正整数拆分成更多的3.
根据n/3得到的余数可以分为以下情况:
1.余数为0,则n=3m(m≥2),则将n拆分成m个3.
2.余数为1,则n=3m+1(m≥1),将n分成m-1个3和2个2.
3.当余数为2的时候,则n=3m+2(m≥1),将n分成m个3和1个2.
上面适用的情况就是n≥4,当n≤3的时候就不适用了。
当n≤3,则结果返回乘积最大是(n-1)。
实现函数代码如下:

int integerBreak(int n) {
    if (n <= 3) {
        return n - 1;
    }
    int quotient = n / 3;
    int remainder = n % 3;
    if (remainder == 0) {
        return (int)pow(3, quotient);
    } else if (remainder == 1) {
        return (int)pow(3, quotient - 1) * 4;
    } else {
        return (int)pow(3, quotient) * 2;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/618276
推荐阅读
相关标签
  

闽ICP备14008679号