口试标题：(3)整数拆分

标题

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以得到的最大乘积 

• 示例 1:
  
  
  
  • 输入: n = 2
    
  • 输出: 1
    
  • 表明: 2 = 1 + 1, 1 × 1 = 1
    
  
  
• 示例 2:
  
  
  
  • 输入: n = 10
    
  • 输出: 36
    
  • 表明: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    
  
  
• 提示:2 <= n <= 58
  

代码

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <string.h>
6. int main()
7. {
8.     while (1)
9.     {
10.         int n;
11.         scanf("%d",&n);
12.         if (n<2 || n>58)
13.             return 0;
14.         int three_n = n/3;
15.         int yushu = n%3;
16.         int end = 1;
17.         if (yushu == 1)
18.         {
19.             three_n--;
20.             for (int i = 0; i < three_n; i++)
21.             {
22.                 end = end * 3;
23.             }
24.             end = end * 4;
25.         }
26.         else if (yushu == 2)
27.         {
28.             for (int i = 0; i < three_n; i++)
29.             {
30.                 end = end * 3;
31.             }
32.             end = end * 2;
33.         }
34.         printf("end = %d\n",end);
35.     }
36.     return 0;
37. }

复制代码

剖析

• 什么数相乘最大
  
  
  
  • 将一个数拆分为多个3，由于3的乘积最大
    
  • 当余数为1的时间，将一个3拆出来合成为4（1+3），乘积最大
    
  • 当余数为2的时间，直接多个3相乘再乘于2的乘积最大
    
  
  

举例

• 9
  
  
  
  • 3*3*3
    
  
  
• 10
  
  
  
  • 3*3*4
    
  
  
• 11
  
  
  
  • 3*3*3*2