A simple explanation of the math part and a O(n) solution
The first thing we should consider is : What is the max product if we break a number N into two factors?\n\nI use a function to express this product: f=x(N-x)\n
The first thing we should consider is : What is the max product if we break a number N into two factors?\n\nI use a function to express this product: f=x(N-x)\n\nWhen x=N/2, we get the maximum of this function.\n\nHowever, factors should be integers. Thus the maximum is (N/2)*(N/2) when N is even or (N-1)/2 *(N+1)/2 when N is odd.\n\nWhen the maximum of f is larger than N, we should do the break.\n\n(N/2)*(N/2)>=N, then N>=4\n\n(N-1)/2 *(N+1)/2>=N, then N>=5\n\nThese two expressions mean that factors should be less than 4, otherwise we can do the break and get a better product. The factors in last result should be 1, 2 or 3. Obviously, 1 should be abandoned. Thus, the factors of the perfect product should be 2 or 3.\n\nThe reason why we should use 3 as many as possible is \n\nFor 6, 3 * 3>2 * 2 * 2. Thus, the optimal product should contain no more than three 2. \n\nBelow is my accepted, O(N) solution.\n\n    public class Solution {\n        public int integerBreak(int n) {\n            if(n==2) return 1;\n            if(n==3) return 2;\n            int product = 1;\n            while(n>4){\n                product*=3;\n                n-=3;\n            }\n            product*=n;\n            \n            return product;\n        }\n    }
[]