面试题目：(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

代码

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>int main()
{while (1){int n;scanf("%d",&n);if (n<2 || n>58)return 0;int three_n = n/3;int yushu = n%3;int end = 1;if (yushu == 1){three_n--;for (int i = 0; i < three_n; i++){end = end * 3;}end = end * 4;}else if (yushu == 2){for (int i = 0; i < three_n; i++){end = end * 3;}end = end * 2;}printf("end = %d\n",end);}return 0;
}

解析

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

举例

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