4 different solutions with thorough explanations in C++, 100%!
1. The naive solution (Time limit exceeded)\nIf I got a similar problem I would start with the naive solution. The naive solution\'s running time is exponential
**1. The naive solution** (Time limit exceeded)\nIf I got a similar problem I would start with the naive solution. The naive solution\'s running time is exponential trying to get the possible value for all of the variations and get the maximum among them.\n```c++\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        return helper(0, 1, n, 0);\n    }\nprivate:\n    int helper(int curSum, int curMult, int target, int depth) {\n        if (curSum == target) return curMult;\n        int maxRes = INT_MIN;\n        for (int i = 1; i < target; i++) \n            if (i + curSum <= target) maxRes = max(maxRes, helper(curSum + i, curMult * i, target, depth + 1));\n        return maxRes;\n    }\n};\n```\n**2. Optimization using memoization** (~680ms)\nAfter solving it naively it\'s time to optimize it. Since it recomputes the same parameters again and again we can prune it \nas we have done it with fibonacci numbers. The key insight here is to add memoization for the parameters which are changing. Now our solution is polynomial. \n```c++\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        return helper(0, 1, n, 0);\n    }\nprivate:\n    struct KeyHasher {\n        size_t operator()(const pair<int, int>& p) const {\n            return (hash<int>()(p.first) << 1) ^ (hash<int>()(p.second));\n        }\n    };\n    unordered_map<pair<int, int>, int, KeyHasher> used;\n    int helper(int curSum, int curMult, int target, int depth) {\n        if (used.find({curSum, curMult}) != used.end()) return used[{curSum, curMult}];\n        if (curSum == target) return curMult;\n        int maxRes = INT_MIN;\n        for (int i = 1; i < target; i++) \n            if (i + curSum <= target) \n                maxRes = max(maxRes, helper(curSum + i, curMult * i, target, depth + 1));\n        used[{curSum, curMult}] = maxRes;\n        return maxRes;\n    }\n};\n```\n**3. Optimization using dynamic programming** (~0 ms)\nHere\'s the DP O(n^2) solution. The key idea here is to find the solution for each solution depending of the previous results. \ndp[i] => is the maximum product value we can get if we divide the number at least to 2 subgroups. For example, dp[2] = 1 which can be\ndivided by 1 * 1, since 1 + 1 = 2. \n**So there are three variations:**\n```c++\nSuppose that our number is n = 4.\n1. dp[i -j] * dp[j]  => that\'s when we represent 4 as [1, 1, 1, 1]  which gives 1\n2. dp[i - j] * j => [1, 1, 2] or [2, 1, 1] which gives 2\n3. (i - j) * j => [2, 2] which gives 4 \nTherefore, dp[4] = 4\n```\n\n```c++\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        vector<int> dp(n + 1, 1);\n        for (int i = 3; i <= n; i++) {\n            for (int j = 1; j < i; j++) {\n                dp[i] = max(dp[i], max({dp[i - j] * dp[j], dp[i - j] * j, (i - j) * j}));\n            }\n        }\n        return dp[n];\n    }\n};\n```\n**4. Mathematical solution** O(log(N)) ~0ms\nHow to understand this solution? Just look at the results for the first 13 values:\n```c++\n\t2 -> 1, 1\n\t3 -> 1, 2\n\t4 -> 2, 2\n\t5 -> 3, 2\n\t6 -> 3, 3\n\t7 -> 3, 4\n\t8 -> 3, 3, 2\n\t9 -> 3, 3, 3\n\t10 -> 3, 3, 4\n\t11 -> 3, 3, 3, 2\n\t12 -> 3, 3, 3, 3\n\t13 -> 3, 3, 3, 4\n```\nIntuitively, we want 3 as many as possible. \n```\n1. n % 3 == 0 => it\'s pow(3, n / 3) \n2. n % 3 == 1 => We don\'t want to have 1 in the result, because it\'s not the optimal variation. What we can do is to break \none of the three\'s into 2 * 2 or 4. Therefore, the result is pow(3, (n / 3 ) - 1 ) * 4;\n3. n % 3 == 2 => If we try to break one of the \'threes\' it turns out that is not effective. Therefore, pow(3, n / 3) * 2 is the answer.\n```\n\n```c++\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        if (n <= 3) return n - 1;\n        if (n % 3 == 0) return pow(3, n / 3);\n        if (n % 3 == 2) return pow(3, n / 3) * 2;\n        return pow(3, (n / 3 ) - 1 ) * 4;\n    }\n};\n```
['Math', 'Dynamic Programming', 'Backtracking']