[C++]LeetCode343.整数拆分

本文主要是介绍[C++]LeetCode343.整数拆分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

343.整数拆分

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

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

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

两个特殊情况：当n=2，Smax=1; 当n=3，Smax=2;
找规律：
n = 4，Smax=22=4; n = 5, Smax=32=6;
n = 6，Smax=33=9; n = 7, Smax=322=12;
n = 8，Smax=332=18; n = 9, Smax=333=27;
n = 10，Smax=3322=36;
因此，我们将n分成最多的3和最少的2，但是不能出现1；
例如n=10时，最多的3为：3331；但是由于1对于求解乘法最大值没有贡献，所以需将后面的31改为2*2；
因为程序中就是求n可以分解3的最多和2的最小个数，返回pow(3, num_3)*pow(2, num_2)即可

public:
    int integerBreak(int n) {
        if(n == 2 || n == 3) return n-1;
        int num3 = 0;
        int num2 = 0;
        while(n > 0)
        {
            num3++;
            n -= 3;
            if(n == 2)
            {
                num2 = 1;
                break;
            }
            if(n == 1)
            {
                num3--;
                num2 = 2;
                break;
            }
        }
        return pow(3, num3) * pow(2, num2);
    }
};

这篇关于[C++]LeetCode343.整数拆分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！