Java O(n) DP solution, store and reuse products
This is an O(n) solution, the idea is to store all previously calculated product, note any n>4 will guarantee to have a factor of 3. Modifed per suggestion of @
This is an O(n) solution, the idea is to store all previously calculated product, note any <code>n>4</code> will guarantee to have a factor of <code>3</code>. Modifed per suggestion of @jianbao.tao and @ericxliu, Thank you!\n\n\n    public int integerBreak(int n) {\n        if (n <= 2) return 1;\n        if (n == 3) return 2;\n        if (n == 4) return 4;\n        int[] p = new int[n+1];\n        p[2] = 2;\n        p[3] = 3;\n        p[4] = 4;\n        for (int i = 5; i <= n; ++i) {\n            p[i] = 3 * p[i-3];\n        }\n        return p[n];\n    }\n\nWhy the max product of any <code>n>4</code> must contain a factor of 3? <br>\n1. It can't contain any factor x that is >= 5, o.w., we can further increase the max product by decomposing x, as the decomposed x when x>=5 is strictly greater than x;<br>\n2. Out of 1, 2, 3, 4, we know 1 won't be a factor of n when <code>n>4</code>, if n is an odd number, 3 must be there as a factor (2 and 4 can't add up to an odd number); <br>\n3. Now say n is an even number (<code>n>4</code>) and only has factor of 2 and 4, we can always split a <code>6</code> to <code>3X3</code>, which is better than <code>2X2X2</code>.<br>\nTherefore, the max product of any n (<code>n>4</code>) must contain a factor of 3. The recurrence relation holds.\n\nFurther, as it holds for all n (<code>n>4</code>), we will be only using 3 as factor for n (<code>n>4</code>), we keep subtracting 3 until <code>n<=4</code>, and adopt the remaining factor. This leads to the closed form answer:\n\n    public int integerBreak(int n) {\n        if (n <= 2) return 1;\n        if (n == 3) return 2;\n        if (n % 3 == 0) return (int)Math.pow(3, (n/3));\n        else if (n % 3 == 1) return 4 * (int)Math.pow(3, (n-4)/3);\n        else return 2 * (int)Math.pow(3, (n-2)/3);\n    }\n\nAs for the complexity of the close form solution, it depends on the implementation of the build-in pow, it could be O(logn) (as a simple O(logn) implementation exists), but not necessarily. The build-in pow could be better than that by using caching or bit level manipulation. I don\u2019t know the answer though.
[]