# 问题 原题链接：[https://leetcode.com/problems/integer-break/](https://leetcode.com/problems/integer-break/) Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. ``` Example 1: Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. ``` ``` Example 2: Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. ``` Note: - You may assume that n is not less than 2 and not larger than 58. # 分析过程 - 输入：一个整数 - 输出：把这个整数拆成若干个整数的和，要求这几个整数积最大，求这个积。 - 思路：写出前几个数的拆分就能发现规律，4 可以拆成 2 和 2，4 以上又是必须得拆开的，因此只可能拆 2 3。 - 求输入 n 拆分后积最大，就是递归求 n - 2 和 n - 3 中比较大的那个。此题也可以用动态规划做。 - 另外[「bestswifter」](https://bestswifter.com)总结出了一种更简单的方法，直接对 3 取余和模，根据规律直接计算。 # 解决方法 递归方法： ```cpp class Solution { public: int _integerBreak(int n) { // 小于等于3的情况都不需要再拆分了 if (n <= 3) { return n; } // 大于3的情况进行拆分 int m2 = _integerBreak(n - 2); int m3 = _integerBreak(n - 3); return m2 * 2 >= m3 * 3 ? m2 * 2 : m3 * 3; } int integerBreak(int n) { // 特殊处理这几种情况 if (n <= 2) { return 1; } else if (n == 3) { return 2; } // 递归 helper int m2 = _integerBreak(n - 2); int m3 = _integerBreak(n - 3); return m2 * 2 >= m3 * 3 ? m2 * 2 : m3 * 3; } }; ``` 直接根据规律计算： ```cpp class Solution { public: int integerBreak(int n) { // 特殊处理这几种情况 if (n == 2) { return 1; } else if (n == 3) { return 2; } // 由于只能拆3和2，因此可以直接和3取余和模 int a = n / 3; int b = n % 3; if (b == 0) { return pow(3, a); } else if (b == 1) { return pow(3, a - 1) * 4; } else if (b == 2) { return pow(3, a) * 2; } assert(0); } }; ```