leetcode343：整数拆分（integer-break）

[carloscn]

问题描述

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

示例 1:

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

示例 2:

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

力扣题目链接 https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.md

[carloscn]

问题分析

如果能够取数据和项的乘积的最大值，那么需要尽量将数据拆分成相同的数据。

比如对于10：

• MUL(1 + 1 + 1 + 1 + .. + 1) = 1, 10项 / 1
• MUL(2 + 2 + 2 + 2 + 2) = 32，5项 / 2
• MUL(3 + 3 + 4) = 36， 3项 / 3 -> 最大
• MUL(4 + 4 + 2) = 32， 3项 / 4
• MUL(5 + 5) = 25， 2项 / 5