O(log n) time with O(1) space complexity, math solution with proofs (don't be afraid :D )
Intuition\n\n1. Small Numbers: For small numbers like 2 and 3, breaking them up doesn\'t help, as  2 = 1 + 1 \rightarrow 1 \times 1 = 1  and  3 = 1 + 2 \rightar
# Intuition\n\n1. **Small Numbers**: For small numbers like 2 and 3, breaking them up doesn\'t help, as $$ 2 = 1 + 1 \\rightarrow 1 \\times 1 = 1 $$ and $$ 3 = 1 + 2 \\rightarrow 1 \\times 2 = 2 $$, which don\'t yield a product greater than the numbers themselves.\n\n2. **Composite Numbers**: For composite numbers like 4, you can break it into $$ 2 + 2 \\rightarrow 2 \\times 2 $$, and the product becomes 4, which is the same as the original number. Similarly, 6 can be $$ 3 + 3 \\rightarrow 3 \\times 3 $$ or $$ 2+2+2 \\rightarrow 2 \\times 2 \\times 2 $$, yielding 9 vs 8, which is greater than 6.\n\n3. **Mathematical Insight**: When you break a number into its constituent parts, the product tends to be maximized when the parts are as equal as possible. This is a mathematical property and can be proven using calculus (e.g. the [Arithmetic Mean-Geometric Mean Inequality](https://www.wikiwand.com/en/AM-GM_Inequality)). See Extra Proof below.\n\n4. **Special Case for 3**: You\'ll find that breaking numbers into 3s (as much as possible) tends to give the maximum product. This is because $$ 3 \\times 3 > 2 \\times 2 \\times 2 $$. See Proof below.\n\n\n# Approach\n\nGiven the mathematical insights above, we can solve this problem more efficiently without using dynamic programming.\n\n1. If $$ n $$ is less than or equal to 3, return $$ n-1 $$ (because for these cases, $$ n-1 $$ will give the maximum product).\n  \n2. Divide $$ n $$ by 3 as many times as possible until $$ n $$ is no longer divisible by 3 or is less than or equal to 4.\n\n3. Multiply the remaining number with the product of all the 3s.\n\n# Proof\n### Maximizing the Product\n\nSuppose you have a number $$ n $$ and you want to split it into $$ k $$ equal parts of $$ \\frac{n}{k} $$. The product of these $$ k $$ numbers would be $$ \\left(\\frac{n}{k}\\right)^k $$.\n\nTo maximize this product, we take the derivative with respect to $$ k $$ and set it to zero:\n\n$$\n\\begin{aligned}\nf(k) &= \\left(\\frac{n}{k}\\right)^k, \\\\\nf\'(k) &= 0.\n\\end{aligned}\n$$\n\n#### Differentiation\n\n1. Differentiate $$ f(k) = \\left(\\frac{n}{k}\\right)^k $$ with respect to $$ k $$ using logarithmic differentiation.\n\n$$\n\\begin{aligned}\n\\ln(f(k)) &= k \\ln\\left(\\frac{n}{k}\\right), \\\\\n\\frac{d\\ln(f(k))}{dk} &= \\ln\\left(\\frac{n}{k}\\right) + k \\left(-\\frac{1}{k}\\right), \\\\\n\\frac{1}{f(k)} \\frac{df(k)}{dk} &= \\ln\\left(\\frac{n}{k}\\right) - 1, \\\\\n\\frac{df(k)}{dk} &= \\left(\\frac{n}{k}\\right)^k (\\ln(n) - \\ln(k) - 1).\n\\end{aligned}\n$$\n\n2. To find the maximum, we set $$ \\frac{df(k)}{dk} = 0 $$:\n\n$$\n\\begin{aligned}\n\\ln(n) - \\ln(k) - 1 &= 0, \\\\\n\\ln\\left(\\frac{n}{k}\\right) &= 1, \\\\\n\\frac{n}{k} &= e, \\\\\nk &= \\frac{n}{e}.\n\\end{aligned}\n$$\n\n### Why 3 is Magical\n\nNow, it\'s not practical to break $$ n $$ into $$ \\frac{n}{e} $$ pieces unless $$ \\frac{n}{e} $$ is an integer. But this gives us an insight: breaking $$ n $$ into pieces of size around $$ e $$ (2.71828...) will yield a high product. Since we can only break $$ n $$ into integer pieces, the closest integers to $$ e $$ are 2 and 3.\n\nLet\'s compare:\n\n- $$ 2^2 = 4 $$\n- $$ 3^2 = 9 $$\n\nOr, for a larger value:\n\n- $$ 2^3 = 8 $$\n- $$ 3^3 = 27 $$\n\nIt\'s evident that 3 yields a larger product. Also, dividing by 3 reduces the number more slowly, allowing for more numbers in the product. Thus, 3 is the "magical" number that maximizes the product when an integer is broken down into $$ k $$ positive integers.\n\n\n# Complexity\n- Time complexity:\n$$O(log(n))$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution:\n    def integerBreak(self, n: int) -> int:\n        if n <= 3:\n            return n - 1\n        \n        product = 1\n        while n > 4:\n            product *= 3\n            n -= 3\n        \n        product *= n\n        \n        return product\n```\n![image.png](https://assets.leetcode.com/users/images/e928b516-e510-46d7-b118-07edc42c7450_1696578119.664852.png)\n\n\n### Extra Proof: equal constitutent parts maximise the product\nSuppose you have a positive integer $$ n $$ that you want to divide into $$ k $$ parts $$ x_1, x_2, \\ldots, x_k $$ such that their sum is $$ n $$:\n\n$$\nx_1 + x_2 + \\ldots + x_k = n\n$$\n\nWe want to maximize the product $$ P = x_1 \\times x_2 \\times \\ldots \\times x_k $$.\n\nUsing the AM-GM inequality, we get:\n\n$$\n\\frac{x_1 + x_2 + \\ldots + x_k}{k} \\geq \\sqrt[k]{x_1 \\times x_2 \\times \\ldots \\times x_k}\n$$\n\n$$\n\\frac{n}{k} \\geq \\sqrt[k]{P}\n$$\n\n$$\nP \\leq \\left( \\frac{n}{k} \\right)^k\n$$\n\nThe inequality tells us that for a fixed $$ k $$, the maximum product $$ P $$ we can get is $$ \\left( \\frac{n}{k} \\right)^k $$, and this maximum is achieved when all $$ x_i $$ are equal, i.e., $$ x_i = \\frac{n}{k} $$ for all $$ i $$.\n\nTherefore, to maximize the product, it\'s best to divide $$ n $$ into $$ k $$ equal parts.\n\n
['Python3']