5 lines 0ms java solution with detailed explanation and proof
Observation and Analysis:\n\n>     2  1 , 1\n>     3  1 , 2\n>     4  2 , 2\n>     5  3 , 2\n>     6  3 , 3\n>     7  3 , 2 , 2\n>     8  3 , 3 , 2\n>     9  3 
Observation and Analysis:\n\n>     2  1 , 1\n>     3  1 , 2\n>     4  2 , 2\n>     5  3 , 2\n>     6  3 , 3\n>     7  3 , 2 , 2\n>     8  3 , 3 , 2\n>     9  3 , 3 , 3\n>     10 3 , 3 , 2, 2    \nif we split n into k1...kt, for each k(1 <= k <= n)\n\n>     1. if k <= 3, f(k) <= k, which means if we still have k to be split, we should use it as a whole.\n>     2. if k > 3, f(k) >= k (k can at least split into 2 and k - 2, k * (k - 2) - k = k(k - 3) >= 0)\n>         therefore, if we have k (k > 3), we must split it to get a bigger product \n>     3. in this situation, if we split k into 1 and k - 1(k - 1 may keep spliting to m1...mt), \n      we can always get a bigger product by adding this "1" to one of the small split number m; \n      therefore, the smallest number that we split is 2\n>     4. Whenever we have a k > 3, we will separate it into small numbers\n>     Finally, all the small numbers will be either 2 or 3.\n\nSolution:\n\n>     suppose we can separate k into k1, k2, ... kt to get the biggest product for k. \n>     1. now we consider k + 1: Since we won't split into k and 1, so we must add this extra 1 to one of the t small numbers.\n>     2. if we add 1 to a "2", then we form a new "3"; if we add 1 to a "3", \n           we must separate it again into two 2s.\n>     3. for the first choice, we will get f(k) / 2 * 3 = 1.5 f(k); \n           for the second choice, we will get f(k) / 3 * 4 = 1.3 f(k)\n>     4. therefore, as long as we have 2, we change a "2" to "3" rather than changing a "3" to two 2s.\n>     5. the whole process will tend to get as much 3s as possible to get bigger product.\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        if (n % 3 == 1) return (int)Math.pow(3, (n - 4) / 3) * 4;// we cannot have a small number that is equal to 1. Then use 4 instead.\n        return (int)Math.pow(3, (n - 2) / 3) * 2;\n    }
['Java']