整数拆分

二 题目

给定一个正整数 n，将其拆分为至少两个正整数的和，
并使这些整数的乘积最大化。

返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

/**
 * @param {number} n
 * @return {number}
 */
const integerBreak = (n) => {
  // 如果是 2 或者 3，直接返回结果
  if (n === 2) {
    return 1;
  } else if (n === 3) {
    return 2;
  }
  let maxProduct = 0; // 最大乘积
  const mid = Math.ceil(n / 2); // 找出中间值

  // 遍历，将有可能的都列举一下
  for (let i = mid; i > 0; i--) {
    let multiplier = i; // 乘数
    let nowNum = n - i; // 剩余数
    // 如果剩余数比乘数还大或者相等，说明可以继续拆
    // 例如 n = 10：5 * 5、4 * 4 * 2、3 * 3 * 3 * 1
    while (nowNum >= i) {
      multiplier *= i;
      nowNum -= i;
      console.log(i);
    }
    // 碰到拆分后最后一项为 1，即 3 * 3 * 3 * 1
    // 说明它可以将 1 加入到最后一次相乘
    if (nowNum === 1) {
      multiplier = multiplier / i * (nowNum + i); 
    } else if (nowNum >= 2) { // 否则大于等于 2 的，直接相乘
      multiplier *= nowNum;
    }
    // 将每次的最大值取出来
    maxProduct = Math.max(maxProduct, multiplier);
  }

  // 返回最大值，搞定完事
  return maxProduct;
};

console.log(integerBreak(3));

/*
  2 -> 1 * 1 -> 1
  3 -> 2 * 1 -> 2
  4 -> 2 * 2 -> 4
  5 -> 3 * 2 -> 6
  6 -> 3 * 3 -> 9
  7 -> 4 * 3 -> 12
  8 -> 4 * 4 / 3 * 3 * 2 -> 16
  9 -> 5 * 4 / 3 * 3 * 3 -> 27
  10 -> 5 * 5 / 4 * 4 * 2 / 3 * 3 * 4 / 2 * 2 * 2 * 2 * 2 -> 36
*/

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。