Java || Recursion || Memoization || Dp || Linear Solution || Optimized Solution
\n\n# Recursion code\n\nclass Solution {\n    public int integerBreak(int n) {\n        return helper(n-1, n);\n        \n    }\n    int helper(int n, int total
\n\n# Recursion code\n```\nclass Solution {\n    public int integerBreak(int n) {\n        return helper(n-1, n);\n        \n    }\n    int helper(int n, int total)\n    {\n        if(n <= 1)\n        return 1;\n        int notpick = helper(n-1, total);\n        int pick = 0;\n        if(total >= n)\n        pick = n * helper(n, total - n);\n\n        return Math.max(pick, notpick);\n    }\n}\n```\n\n# Rcursion + Memoization\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        return helper(n-1, n, dp);\n    }\n    int helper(int n, int total, int dp[])\n    {\n        if(n <= 1)\n        return 1;\n        int notpick = helper(n-1, total, dp);\n        int pick = 0;\n        if(total >= n)\n        pick = n * helper(n, total - n, dp);\n        \n        return dp[n] = Math.max(pick, notpick);\n    }\n}\n```\n\n# Dp code\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        \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# Linear Solution\n```\nclass Solution {\n    public int integerBreak(int n)\n    {\n        if (n == 2 || n == 3) return n-1;\n        int res = 1;\n        while (n>4){\n            n -= 3;\n            res *= 3;\n        }\n        return (n*res);\n    }\n}\n```\n\n# Optimized Solution\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 (int)(Math.pow(3,n/3 - 1))*4;\n        else if(n%3==2)\n            return 2*((int)Math.pow(3,n/3));\n        else\n            return (int)Math.pow(3, n/3);\n    }\n}\n```\n
['Math', 'Dynamic Programming', 'Recursion', 'Memoization', 'Java']