3 Approach || DP || linear || Formula based
\n# Code 1\nDynamic programming approach \nTime Complexity  - O(N2)\nSpace Complexity - O(N)\n\nclass Solution {\n    public int integerBreak(int n) {\n        
\n# Code 1\nDynamic programming approach \nTime Complexity  - O(N*2)\nSpace Complexity - O(N)\n```\nclass Solution {\n    public int integerBreak(int n) {\n        int[] dp = new int [n+1];\n        dp[0]=0;\n        dp[1]=0;\n        dp[2]=1;\n        for (int i=3;i<=n;i++)\n            for (int j=1;j<=i;j++)\n                dp[i] = Math.max(dp[i], j*Math.max(dp[i-j],i-j)); \n                \n        return dp[n];\n    }\n}\n```\n\n\n# Code 2\nn = 1 => we get max value only when we divide 1 into 0 and 1\nn = 2 => we get max value only when we divide 2 into 1 and 1\nn = 3 => we get max value only when we divide 3 into 1 and 2\nn = 4 => we get max value only when we divide 4 into 2 and 2\nn = 5 => we get max value only when we divide 5 into 2 and 3\nn = 6 => we get max value only when we divide 6 into 3 and 3\nn = 7 => we get max value only when we divide 7 into 4 and 3\nn = 8 => we get max value only when we divide 8 into 2, 3 and 3\nn = 9 => we get max value only when we divide 9 into 3, 3 and 3\nn = 10 => we get max value only when we divide 10 into 4, 3 and 3\n\nFrom here we can see that upto n=7 we have different values but after n=7 we can just multiply 3 to n-3 to get the max value.\n\n\nTime Complexity : O(N)\nSpace Complexity : O(1)\n```\nclass Solution {\n    public int integerBreak(int n)\n    {\n        if (n == 2 || n == 3) return n-1;\n        int result = 1;\n        while (n>4){\n            n -= 3;\n            result *= 3;\n        }\n        return (n*result);\n    }\n}\n```\n\n# Code 3\n\nFrom code 2 Explanation we can simplify code more  \n1. n<=3  => ans =n-1\n2. n%3 is 1 => maximum value should be 4 * 3**((n/3 - 1)\n3. n%3 is 2 => maximum value should be 2 * 3**(n/3)\n4. n%3 is 0 => maximum value should be 3**(n/3)\nSimple Mathematics\nTime Complexity : O(1)\nSpace Complexity : O(1)\n```\nclass Solution {\n    public int integerBreak(int n) {\n        if(n<=3)\n            return n-1;\n        else if(n%3==1)\n            return pow(3,n/3 - 1)*4;\n        else if(n%3==2)\n            return 2*pow(3,n/3);\n        else\n            return pow(3, n/3);\n    }\n};\n```
['Math', 'Dynamic Programming', 'Java']