✅Beats 100% | O(n) Easy Solution🔥 | Why 3s why not 4s or else, explained in short and easy 🚀
Do upvote if you like the  solution and explanation please \uD83D\uDE80\n\n---\n\n\n# First Understand Why 3s why not 4s or else ?\n- The reason we use 3s inste
# Do upvote if you like the  solution and explanation please \uD83D\uDE80\n\n---\n\n\n# First Understand Why 3s why not 4s or else ?\n- The reason we use 3s instead of 4s is to maximize the product. When you break a number into smaller numbers, multiplying several smaller numbers together results in a larger product than multiplying larger numbers together.\n\n- Breaking a number into 3s is generally the best strategy because:\n\n-  2 * 2 * 2 < 3 * 3: Multiplying three 3s together is greater than multiplying three 2s together.\nUsing 4s is less efficient because 4 * 4 is equal to 2 * 2 * 2 * 2, which has the same product as four 2s. Therefore, breaking into 4s is less optimal in terms of maximizing the product.\nSo, we prefer breaking the number into as many 3s as possible, with possibly a few 2s left over. This is why we use 3s instead of 4s in the dynamic programming solution.\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to break an integer n into the sum of positive integers and maximize their product. To do this, we need to find a pattern that leads to the maximum product. We can observe that breaking n into as many 3s as possible will generally yield the maximum product. However, there are some exceptions when using 2s can be more beneficial.\n\n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. If n is less than or equal to 3, we return n - 1 because the maximum product for integers 2 and 3 is simply 2 and 3, respectively.\n\n2. For integers greater than 3, we use dynamic programming to calculate the maximum product. We initialize an array dp to store the maximum product for each integer from 2 to n.\n\n3. We loop through the integers from 4 to n and calculate the maximum product for each integer i by considering two options:\n\n4. Breaking i into i - 2 and multiplying it by 2.\nBreaking i into i - 3 and multiplying it by 3.\nWe take the maximum of these two options and store it in dp[i].\n\n5. Finally, we return dp[n], which contains the maximum product for integer n.\n\n---\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this solution is O(n) because we iterate through the integers from 4 to n once, and for each integer, we perform constant time operations.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n) because we use an array dp of size n + 1 to store the maximum product for each integer from 2 to n.\n\n---\n\n# Code\n```\nclass Solution {\npublic:\n    int integerBreak(int n) {\n        if (n <= 3) return n - 1;\n        \n        vector<int> dp(n + 1, 0);\n        dp[2] = 2;\n        dp[3] = 3;\n        \n        for (int i = 4; i <= n; ++i) {\n            dp[i] = max(dp[i - 2] * 2, dp[i - 3] * 3);\n        }\n        \n        return dp[n];\n    }\n};\n\n```
['Array', 'Math', 'Dynamic Programming', 'C', 'Python', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript']